탐색

탐색은 개념 자체는 어렵지 않다. 현재 가지고 있는 데이터를 얼마나 효율적으로 순회하면서 찾고 있는 데이터를 찾아내느냐의 문제이다.

대표적으로 두가지 방법이 있는데, 하나가 선형 탐색이고, 두번째가 이분 탐색이다.

이 두가지 방법을 구분하는 대표적인 요인은, 데이터가 정렬되어있는가 아닌가의 여부이다.

선형 탐색

그냥 모든 데이터를 다 뒤져가면서 값을 찾아내는 알고리즘이다. 알고리즘이라 부르기도 민망할 정도인데, for 문을 한번만 돌리면 구현 가능하다.

시간복잡도는 O(n) 이며, 코딩테스트에서는 10억 이상의 데이터가 주어졌다고 하면 이 알고리즘으로는 불가능하겠구나 생각하면 될듯하다.

이진(이분) 탐색

데이터가 정렬되었을 때만 사용할 수 있는 탐색 방법이다. 선형탐색과 다르게 정렬이 되어있으므로 내가 찾는 데이터를 기준으로 탐색하는 값과 비교하는 것을 통해, 방금 탐색한 값이 target_value 보다 크다면 이보다 큰 값들은 탐색하지 않고도 전부 배제할 수 있다. 반대도 마찬가지이다. 내가 방금 탐색한 값이 target_value 보다 작다면, 현재 탐색한 값보다 작은 값들을 모두 배제할 수 있다.

이런식으로 찾아나가는 방법을 이분 탐색이라 한다.

def solution(array, target_value):
    array.sort()
    left, right = 0, len(array) - 1

    while left <= right:
        mid = (left + right) // 2
        if array[mid] > target_value:
            left = mid + 1
        elif array[mid] < target_value:
            right = mid - 1
        else:
            return mid

    return -1

target_value 를 찾으면 반환하고, 찾지 못하면 -1을 반환하는 간단한 이분탐색 코드이다. 문제는 코드는 간단하지만 문제가 괴랄하다는 것.