CS 기본/자료구조

이분 탐색

LTSGOD 2023. 10. 23. 00:18

이분 탐색(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) 헷갈리지 않게 구현하기

개요 이분 탐색은 off-by-one error가 발생하기 쉬워서 늘 헷갈립니다. 이분 탐색 문제를 풀다보면 탈출 조건으로 lo <= hi, lo < hi, lo + 1 < hi 중 어느 걸 선택해야 할 지, 정답이 lo인지 hi인지 (lo + hi) / 2

www.acmicpc.net

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)

이진 탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는

velog.io