이진탐색

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

이분 탐색은 정렬된 데이터에서 값을 빠르게 찾는 방법 중 하나입니다. 일반적인 방법으로 위와 같은 Int 배열에서 "9" 를 찾는다고 가정하면, O(n) 시간 복잡도를 가집니다. 이분 탐색은 첫 인덱스가 아닌 중간부터 값을 비교하여 탐색할 구간을 정합니다. start, mid, end 가 기준점이 되어 구간을 선택하고, 필요 없는 구간은 탐색하지 않기 때문에, O(logN) 의 시간 복잡도를 가집니다. 주의점으로는 "정렬되어 있는 데이터" 에서만 사용이 가능하다는 점입니다. 비정렬된 상태에서 사용될 때 정렬 알고리즘 + 이분 탐색 방법이 더 효율적일지, 혹은 선형 탐색 알고리즘이 더 나을지는 개발자의 판단이 필요합니다. 다음으로는 이분 탐색의 활용으로 파라메트릭서치(Parametric Search) 와 ..