이분 탐색 (Binary Search)

이분 탐색

탐색 범위를 두 부분으로 분할해서 찾는 방식. 따라서 전부를 탐색하는 것에 비해 속도가 빠름

시간 복잡도 O(log(n))

 

1. 이미 정렬이 되어있어야 이분 탐색 가능

2. left, right로 mid 값을 결정

3. mid 값과 구하고자 하는 값 비교

4. 비교할 때 mid 값보다 구하고자 하는 값이 크면 left를 mid + 1로, 낮으면 right를 mid-1로 만듦

5. left > right 가 될 때 까지 위의 과정을 반복해 구하고자 하는 값 찾음