[Algorithm] Binary Search (이분 탐색)

Binary Search (이분 탐색 / 이진 탐색)

정렬된 배열에서 특정 값을 찾는 알고리즘

 

시간복잡도

O(logN)

 

알고리즘

이분 탐색은 내가 찾고자 하는 값(key)과 배열의 중간 값을 비교한다.

 

이 때, key가 더 크다면, 중간 값 이후의 값들만이 탐색 대상이 된다.

반대로, key가 더 작다면, 배열의 중간값 이전의 범위가 다음 탐색의 범위가 되는 것이다.

 

이렇게 탐색의 범위를 1/2씩 줄여 나간다. (-> 시간복잡도가 logN이 되는 이유)

 

lo 와 hi의 초기 값은 각각 0, arr.size()-1 이다.

1. 중간 인덱스 구하기
   • mid = (lo + hi) / 2
2. 내가 찾는 값과 중간 값(중간 인덱스에 위치한 값) 비교하기
   • arr[mid] vs key
3. 비교 결과에 따라 다음 탐색 범위 정하기
   1. arr[mid] > key -> hi = mid-1;
   2. arr[mid] < key -> lo = mid+1;
   3. arr[mid] == key -> return true; (찾고자 하는 값을 찾았으므로 종료)
4. 1~3 반복

 

이미지 클릭시 출처 사이트로 이동

 

위 이미지의 사이트에서 최악/최선의 경우를 모두 확인할 수 있습니다.

 

 

---

관련 문제 - [백준] 1920 수 찾기

아래 포스트에서 확인할 수 있습니다.

[백준] 1920 수 찾기 (Java)