[알고리즘 전략] 이분탐색

** [한권으로 합격하는 취업 코딩테스트] 책을 참고해 작성했습니다.

** 주의점, 기억해야할 것을 위주로 작성합니다. 

 

선형 탐색 Linear Search 

 

- 순차탐색의 다른 말 

- 배열에 여러 값들을 넣어 두고, 그 중에서 어떤 값을 찾을 때 반복문을 돌려 하나하나 비교하며 찾는 것 

- O(N)

 

이분 탐색 Binary Search 

 

- 탐색할 부분이 하나만 남을 때까지 탐색 범위를 줄여가는 방식 

- 조건: 정렬된 배열

- left = 0 , right = len(arr)-1, mid = (left + right) // 2로 하는 게 일반적. 

- arr[mid] > target 이면 왼쪽 탐색 (right = mid - 1) 

- arr[mid] < target 이면 오른쪽 탐색 (left = mid + 1) 로 설정해 진행한다. 

- O(logN)

* 파이썬 라이브러리 bisect 

from bisect import bisect_left, bisect_right 
arr = [2,3,6,6,6,10,12,15] 
l = bisect_left(a, 6) 
r = bisect_right(a, 6) 
print(r-l) # 3

- l: 탐색할 부분의 왼쪽 포인터/ h: 탐색할 부분의 오른쪽 포인터/ t: 목표 값

- bisect_left(l, t): 목표 값보다 같거나 큰, 첫번째 값의 위치 반환 

- bisect_right(l, t): 목표 값보다 큰, 첫번째 값의 위치 반환 

- bisect_right() - bisect_left() = 배열에 목표 값이 몇개가 있는지도 알 수 있다.