이진탐색 알고리즘(Upper Bound, Lower Bound) 기본 개념 Java

이진탐색은 사전처럼 탐색할 대상이 정렬되어 있는 상태에서 사용한다.

대상을 둘로 나눠 절반씩 줄여나가는 원리이다.

 

이진탐색 기본 알고리즘은 중복이 없으며, 반드시 존재하는 데이터를 탐색할 때 용이하다.

Upper Bound은 중복이 존재하거나 없는 데이터를 탐색할 경우, 바로 다음 결과값을 반환한다. 가장 오른쪽 위치를 구한다.

Lower Bound는 중복이 존재하거나 없는 데이터를 탐색할 경우, 일치하는 숫자가 가장 처음 나타나는 값을 반환한다. 가장 왼쪽 위치를 구한다.

이 원리를 이용하면 중복 갯수를 구할 수 있다.