이분 탐색(Binary Search)

이분 탐색(Binary Search)

• 이진 탐색 혹은 이분 탐색 이라고 부름

• 자료 구조에서 특정 값을 찾을 때, 탐색 범위를 절반씩 나눠가면서 해당 값을 찾아가는 것

• 탐색 범위를 두 부분으로 분할하면서 찾는 방식

• 일반적인 탐색 알고리즘 보다 빠름

시간 복잡도

• 전체 탐색 : O(N)

• 이분 탐색 : O(logN)

진행 순서

1. 정렬

2. left, right 값 설정(보통 left 에 찾으려는 최소값, right에 최대값)

3. mid = (left + right) / 2 로 mid 값 설정

4. 구할값이 mid 보다 크면 left = mid + 1

5. 구할값이 mid 보다 작으면 right = mid - 1

6. right < left 가 될때까지 반복

7. 결과를 찾은 경우, 찾은것을 반환. 결과를 찾지 못한 경우에는 -1을 반환한다.

출처 : https://github.com/WooVictory/Ready-For-Tech-Interview/blob/master/Algorithm/%EC%9D%B4%EB%B6%84%20%ED%83%90%EC%83%89(Binary%20Search).md