•
이진 탐색 : 정렬된 숫자열에서 특정한 값의 위치(인덱스)를 찾는 기법으로 중간값을 비교하여 그보다 큰지 작은지 확인 후 범위를 좁혀 탐색하는 방식이다. 큰 범주로 본다면 분할 정복에 속하지만 이진 탐색에 해당하는 문제가 많아 따로 정리하였다.
일반적인 탐색은 시간 복잡도 O(n)을 갖지만 이진 탐색을 통하면 O(log n)의 시간 복잡도를 가져 훨씬 빠르게 탐색할 수 있다. 정렬된 어떤 값들 중에 특정 값을 찾는 문제는 이진 탐색을 우선적으로 생각해야 한다.
•
이진 탐색을 함수로 구현할 때, 등호의 위치에 따라 같은 값의 좌측과 우측이 결정되고 인덱스에 따라 start = mid + 1을 하게 되면 기준의 오른쪽이 end = mid - 1을 하게 되면 기준의 왼쪽이 출력 된다. 둘 다 붙이게 되면 start는 기준의 오른쪽 end는 기준의 왼쪽이 출력 되지만 문제의 등호 조건이 바뀌게 된다.
예시 : [1,2,3,3,4,5,5] 에서 3 찾기