정렬(sort)과 탐색(search)

1) 정렬(sort)이란 여러 원소로 주어진 데터를 정해진 기준에 따라 늘어놓는 작업을 말한다.

Python의 경우 list를 사용하면 굳이 정렬 알고리즘을 구현하지 않아도 된다.(Java도 마찬가지)

1. 파이썬 내장 함수 : sorted() // 이는 새로운 list를 만들어냄 ex. L2=sorted(L1)
2. list 메서드 : .sort()

2) 탐색(search)이란 여러 원소에서 특정한 값을 찾아내는 작업을 말한다.

1. 선형 탐색 (linear search) : 모든 원소에 대해 순차적으로 비교하며 찾는 작업이다. 이는 배열의 길이에 비례하는 소요시간이 걸리며, 시간 복잡도는 O(N)으로 최악의 경우엔 모든 원소를 다 검사해야 한다.
2. 이진 탐색 (binary search) : 정렬되어 있는 배열에 한해서 사용할 수 있는 탐색이다. 이때 필요한 데이터는 처음(lower)과 끝(upper) 그리고 중간(middle) 값이 필요하며, 선형 탐색에 비해 탐색 시간이 짧다. 시간 복잡도는 O(logN)

def solution(L, x):
    lower = 0
    upper = len(L)-1
    middle = -1
    
    while lower<=upper:
        middle = (lower + upper)//2 
        
        if x==L[middle] :
            return middle
        elif L[middle]<x :
            lower = middle + 1
        else : 
            upper = middle - 1
    
    return -1

 

O(log n)은 이상적인 소요시간이며, 길이에 따라 O(n)에 비해 훨씬 짧음을 알 수 있다.

사진 출처 : https://velog.io/@qksud14/Algorithm-BigO