들어가며 순차 탐색 vs 이분 탐색 배열에서 특정 값을 찾는 가장 쉬운 방법은 배열의 맨 앞에서부터 차례대로 찾아나가는 방법입니다. 이는 순차 탐색(Sequential Search) 혹은 선형 탐색(Linear Search) 이라고 하며 최대 n개의 원소들을 확인해야 하므로 O(n)의 시간복잡도를 가집니다. 하지만 배열이 오름 차순이나 내림 차순으로 정렬되어 있음이 보장된다면, 이 정보를 활용해 특정 값을 더 빠르게 찾을 수 있습니다. 예를 들어, 오름 차순으로 정렬된 A = [?, ?, ?, 16, ?, ?, ?] 라는 배열이 존재할 때, 15라는 값이 배열 내 몇 번째에 존재하는지 찾고자 한다고 가정할게요. 이 때, 배열의 3번 인덱스 즉, index = 3을 탐색했을 때, A[3] = 16입니다.