이진 탐색이란?

· 정렬된 리스트의 중앙에 있는 키 값을 조사하여 찾고자하는 레코드가 왼쪽에 있는지 오른쪽에 있는지를 알아내어 탐색의 범위를 반으로 좁혀가는 방법.

· 반드시 정렬된 리스트여야 하며 고정된 데이터에 적합하다. 따라서 데이터의 삽입이나 삭제가 빈번할 시에는 적잡하지 않다.

이진 탐색의 비교 횟수

시간 복잡도

이진 탐색 코드 (Java)

public void binarySearch(int[] array, int num) {
	int left = 0;
	int right = array.length - 1;
	int mid = 0;
		
	while(left <= right) {
		mid = (left + right) / 2;
			
		if(num == array[mid]) {
			System.out.println("찾으시는 숫자 " + num + "을 찾았습니다. " + (mid + 1) + "번째에 있었습니다.");
			break;
		} else if(num < array[mid]) {
			right = mid - 1;
			mid = (left + right) / 2;
		} else {
			left = mid + 1;
			mid = (left + right) / 2;
		}
	}
}