이분 탐색 ( Binary Search / Swift ) - 1

 이분 탐색은 정렬된 데이터에서 값을 빠르게 찾는 방법 중 하나입니다.

 

일반적인 방법으로 위와 같은 Int 배열에서 "9" 를 찾는다고 가정하면, O(n) 시간 복잡도를 가집니다. 

 

이분 탐색은 첫 인덱스가 아닌 중간부터 값을 비교하여 탐색할 구간을 정합니다.

 

start, mid, end 가 기준점이 되어 구간을 선택하고, 필요 없는 구간은 탐색하지 않기 때문에,

 

O(logN) 의 시간 복잡도를 가집니다. 

 

 

 

주의점으로는 "정렬되어 있는 데이터" 에서만 사용이 가능하다는 점입니다.

 

 

비정렬된 상태에서 사용될 때 정렬 알고리즘 + 이분 탐색 방법이 더 효율적일지,

 

혹은 선형 탐색 알고리즘이 더 나을지는 개발자의 판단이 필요합니다.

 

 

 

 

다음으로는 이분 탐색의 활용으로 파라메트릭서치(Parametric Search) 와

 

상한, 하한선 (Lower Bound, Upper Bound) 에 대해 포스팅하겠습니다.