이분 탐색
이분 탐색 알고리즘 헷갈리는 내용 정리(while 조건, lo/hi 갱신 처리, 반환 값, lo/hi 범위)
이분 탐색을 이용한 백준 문제들을 풀다가 헷갈리는 부분들이 생겨 그에 관해 정리해본다. 일단 이분 탐색 알고리즘의 대표적인 코드를 한번 보자. int BinarySearch(int lo, int hi, int target) { while(lo + 1 < hi) { int mid = (lo + hi) / 2; if(arr[mid] target) hi = mid; } return lo; } 여기서 헷갈리는 부분들이 4가지가 있었다. while문 안의 조건 다른 사람들의 이분 탐색 코드를 살펴보면, 대표적으로 많이 쓰이는 3가지가 있다. (lo + 1 < hi), (lo < hi), (lo = target 라면, hi = mid로 갱신을 해줘야한다. while문을 탈출하는 lo + 1 == hi의 경우에, h..