이분 탐색의 이해

 이분탐색은 간단하게 절반씩 줄여나가며 값을 찾는 방법이다.
논리는 중학생도 이해할 수 있는 간단한 로직이다. 그러나 문제를 풀다보면 lo < hi 인지 lo <= hi 인지 등 헷갈리는 경우가 많고 lo = mid 인지 lo = mid + 1로 갱신해야하는지 잘 모를 때가 있다. 
 
https://www.acmicpc.net/blog/view/109

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

 이분탐색에 대한 정말 좋은 글이다. 이 글을 정독하고 정리를 했다.
먼저 가장 좋은 방법은 while(lo + 1 < hi) 이다. 이렇게 하면 lo, hi 모두 mid로 갱신하면 문제를 풀 수 있다. mid 값을 + 1 or -1 로 갱신했던 이유는 결국 무한루프에 빠지는 것을 막기 위함이다. 
 
lo + 1 < hi 를 해놓으면, 언제나 lo < mid < hi 를 보장할 수 있다. lo = hi 이면 while 조건에 의해 탈출하게 될 것이기 때문이다. 이 방법이 가장 간단하고 오류없이 찾을 수 있는 방법인 것 같다.