• 알고리즘: 어떤 일을 하기 위한 명령의 집합

✔️ 이진 탐색(binary search)

: 가능한 가장 적은 횟수로 원하는 원소의 위치를 찾아내어 검색 속도를 빠르게 할 수 있는 알고리즘

• 입력: 정렬된 원소 리스트

• 출력: 원하는 원소의 위치 | null

• 최대 $log_2$ n (= $log$ n )번 소요

• 실행 시간(검색에 필요한 비교 횟수의 평균 값, running time) : 로그 시간(logarithmic time) [ O($log$ n) ]

• 검색에 실패한 경우: $⌈log$(n+1)$⌉$회

  • (⌈ x ⌉: 천장(올림) 메서드; x보다 크거나 같으면서 가장 작은 정수)

• 검색에 성공한 경우: $log$ n - 1 회

• 단순 탐색(simple search): 순서대로 모두 추측하는 것

*배열(array): 원소를 저장할 수 있는 상자들이 일렬로 늘어선 것

이진 탐색 예제 1

package codingTest;

public class Example01 {

	// 이진 탐색
	public static int binarySearch(int[] list,  int item) {
		
		int low = 0;	// 배열의 시작 인덱스(== 탐색 범위의 제일 하위 인덱스)
		int high = list.length - 1;	// 배열의 끝 인덱스(탐색 범위의 제일 상위 인덱스)
		
		while(low <= high) {	// 배열의 시작 인덱스와 끝 인덱스가 다를 경우
			
			int mid = (low + high) / 2;	// 배열에서 중간 인덱스(== 탐색 범위에서 중간 인덱스)
			int guess = list[mid];	// 추측 값
			
			if(guess == item) {	// 추측 값 == 원하는 값
				return mid;
			}
			else if(guess > item) {	// 추측 값 > 원하는 값
				high = mid - 1;
			}
			else {	// 추측 값 < 원하는 값
				low = mid + 1;	// 
			}
		}
		
		return -1;	// 찾는 값이 없을 경우
	}
	
}

package codingTest;

// 실행 클래스
public class MainClass {

	public static void main(String[] args) {
		
		int[] myList = {1, 3, 5, 7, 9};
		
		int result = Example01.binarySearch(myList, 7);
//		int result = Example01.binarySearch(myList, -3);

		System.out.println(result);
	}
	
}