binarySearch

정렬 되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법

• 탐색 범위를 두 부분으로 분할하여 찾는 방식.
• 선형 자료구조 (배열, 벡터 등)이 이미 정렬되어있어야 한다.

binarySearch의 시간복잡도

• 찾아야 하는 대상의 범위가 계속해서 반으로 줄기 때문에 O(lgN)에 동작하도록 할 수 있다.

구현 개념

• st와 en 변수 두 가지를 둔다. st+en/2로 mid를 둔다.
• mid를 둘 때, st+en의 합이 홀수일 경우, 버린다. ex) st+en = 9 mid = 4
• mid보다 큰 경우 st = mid + 1
• mid보다 작은 경우 en = mid - 1