이진탐색
이진탐색은, 찾아야하는 수의 범위 중 가운데의 값과 찾고자 하는 값을 비교하여 대소관계에 따라 특정 구간으로 이동하는 것을 반복하는 것이다.
이진탐색을 사용하는 이유는 순차탐색보다 더 빠르기 때문이다. 실제 이진탐색의 시간복잡도는 O(logN)이다.
루프를 한 번 돌때 마다, 우리가 다루는 구간의 길이는 반으로 감소하고, 구간의 길이가 1이 될 때 까지 계속 반복해서 탐색하는 것을 볼 수 있다. 즉, 루프는 약 번 돌게 된다. 루프 내부 연산의 시간 복잡도는 이기 때문에, 자연스럽게 시간복잡도는 이 되는 것을 볼 수 있다.
과
그러나 모든 상황에서 이진탐색이 유리한 것은 아니다. 이진탐색이 갖고 있는 단점이라면 반드시 정렬이 되어야 한다는 것입니다. 따라서 배열이 정렬된 상태가 아니라면, 정렬을 하기 위해 추가적인 연산을 필요로 한다.
정렬을 추가로 진행한다면, 퀵 정렬 같은 알고리즘을 활용했을 때 이 추가적으로 사용 되기 때문에 오히려 순차탐색에 비해 느려진다. 따라서 정렬된 경우엔 반드시 이진탐색을 사용하는 것이 효율적이겠지만, 그렇지 않은 경우라면 이진탐색을 사용하기 전에 한번 더 생각해보아야 한다. 만약 탐색을 여러 번 진행해야 한다면 이진탐색을 사용하는 것이 좋겠지만, 가장 큰 값을 찾는다거나, 값을 딱 한개만 찾는다면 굳이 이진탐색을 사용할 이유가 없을 것이다.
만약 내가 찾는 값 target이 배열에 여러 개 있다면, 이진탐색을 돌렸을 때 어떤 위치가 나오게 될지는 아무도 모른다. 이런 경우에 보통 사용하는 것이 Lower Bound 이다.
Lower Bound는 원하는 값 target 이상의 값이 최초로 나오는 위치를 의미한다. 이는 바꿔말해 target보다 같거나 큰 원소의 위치들 중 가장 작은 값을 출력해야 한다는 것이다.
Upper Bound
Upper Bound는 원하는 값 target을 초과하는 값이 최초로 나오는 위치를 의미한다.