이분 탐색(Binary Search)

배열에서 원하는 key 값을 찾는다.

 

1. 검색할 정렬된 배열과, 원하는 key 값, 배열의 길이가 필요

( BSearch(int arr[], int key, int size) )

2. 검색의 범위 start 에서 end 까지 설정

start = 0, end = size -1 로 잡는게 편함

 

3. 이분 탐색은 start~end 구간을 설정한 뒤, 구간의 길이를 절반씩 줄이며

start와 end가 구간의 경계에 계속해서 위치하도록 만들어야함.

4. start+1 < end 인 동안 [start, end] , mid = (start+ end)/2 를 구해서

mid < key 이면 [mid, end] 로, mid > key 이면 [start, mid] 로 구간을 줄여 나간다.

start + 1 < end 인 동안 반복하기 때문에 start와 end 사이 무조건 한 칸 이상이 남고, start < mid < end 도 항상 성립

결국 언젠가는 start+1 == end 가 되어 반복 탈출함