탐색 알고리즘 - 이분탐색

탐색 알고리즘의 종류로는 선형, 이분, 해시, BST가 있지만, 이 글은 이분 탐색에 대해 다룰 예정.

이진탐색이란?

이진 탐색 알고리즘은 오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘이다

Upper Bound

탐색 범위의 끝 지점을 의미하며, 값이 존재 할 수 있는 가장 큰 인덱스를 나타낸다. 중간 지점 mid 위치의 값이 비교하고자 하는 값 보다 이하 일 때 반복

Lower Bound

Lower bound는 이분 탐색에서 탐색 범위의 시작 지점을 의미합니다. 즉, 값이 존재할 수 있는 가장 작은 인덱스를 나타냅니다. 중간 지점 mid 위치의 값이 비교하고자 하는 값 보다 작을 때 반복

동작

mid 위치의 값과 찾고자 하는 값을 비교
찾고자 하는 값이 mid보다 크면 low = mid + 1.
찾고자 하는 값이 mid보다 작으면 high = mid - 1.

while (min < max) {
	mid = (max + min) / 2;
	long data = 0;

    if(M < data) {
    	max = mid;
    } else {
    	min = mid + 1;
    }
}