이분 탐색

이분 탐색(binary Search)

• 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
• 데이터가 정렬되어야지 사용할 수 있음.
• 시간복잡도 O(log n)
• start, mid, end 가 존재

ex) 17, 28, 43, 67 , 88, 92, 100 에서 43을 찾아보자

 

 

여기서 끝나면 아쉽다. 위 같은 경우는 쉽지만 이분 탐색 하면 항상 헷갈리는 조건들이 존재

 

요약

1. [s, e]가 Check(s) != Check(e)가 되도록 구간을 설정
2. while (s + 1 < e)동안 mid = (s + e) / 2에서 Check(mid) = Check(s)라면 s = mid, 아니라면 e = mid
3. 구한 경계에서 답이 s인지 e인지 생각해보고 출력

(1에서 경계는 항상 [s, e] 내에 존재하고, 2에서 Check(s), Check(e)는 변하지 않으며, 3에서 s + 1 >= e이고, s < mid < e에서 s < e이므로 s + 1 == e를 만족합니다)

 

위의 예시에서 생각해보자.

 

 

참고

https://www.acmicpc.net/blog/view/109

이분 탐색(Binary Search) 헷갈리지 않게 구현하기

https://velog.io/@kimdukbae/%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-Binary-Search

[알고리즘] 이분 탐색 / 이진 탐색 (Binary Search)