이진 탐색

• 이진 탐색은 로그와 밀접한 관련이 있다는 것이 밑의 식으로 나타난다.
• 이진 탐색을 하기 위해서는 항상 정렬되어 있어야 한다.
• 정렬된 데이터의 중간 숫자를 찾고 그 수보다 크면 작은수를 버리고 작으면 높은 수를 버리는 식으로 진행됨.

n = 정렬된 데이터의 수 , 비교 회수 m

자바의 이진 탐색 알고리즘

• Java에선 메서드가 이미 구현되어 있음 (binarySearch)
• 정렬된 배열 또는 리스트에 적합한 고속 탐색 방법
• binarySearch를 사용 했을 시 해당 key를 찾으면 그 위치를 리턴,
• 그렇지 않으면 -Insertion point-1 값을 리턴합니다. Insertion point가 어떻게 정의되는지도 위에 나와 있는데요.

Insertion point = 그 인덱스에 들어가면 정렬이 유지되는 위치

이진 탐색 알고리즘 구현 (Insertion point는 구현x, 값을 못찾으면 -1로 반환)

1. 재귀적 탐색

int binarySearch1(int[] arr, int key, int lowIndex, int highIndex) {
	int mid;
    
    if(lowIndex <= highIndex) {
    	mid = (lowIndex+highIndex) / 2;
        if(key == arr[mid]) { 
        	return mid;
        }
        else if (key < arr[mid]) {
        	return binarySearch1(arr, key, lowIndex, mid-1);
        } else {
        	return binarySearch1(arr, key, lowIndex, mid+1);
        }
    }
    return -1;
}

2. 반복 탐색

int binarySearch2(int[] arr, int key, int low, int high) {
	int mid;
	while(low <= high) {
		mid = (low + high) / 2;

		if(key == arr[mid]) {
			return mid;
		} else if(key < arr[mid]) {
			high = mid - 1;
		} else {
			low = mid + 1;
		}
	}

	return -1; // 탐색 실패 
}