TIL16/05/21 (Binary Search)

김장인의 국밥집을 며칠을 본지 모른다....
강의를 들을땐 풀어볼 수 있겠다 싶었는데..
다시 꺼내 보니.. 이해하는데 시간이 많이 걸린것 같다.

범위를 반씩 쪼개면서 탐색한다!!!!
log n의 시간 복잡도를 가진다.
이진탐색의 핵심은 시작점 끝점 중간점이다.

시작점과 끝점은 찾는 데이터의 범위를 좁히는 역할을 해주고
중간점은 아주 중요한 조절자 역할을 한다. 결국 중간값이 답이다.

값을 옮길때는 -1이나 +1을 해줌으로써 중간값이 중복탐색해주는 것을 방지하는 것 같다.

max = mid -1;
min = mid +1;