이진 검색

---

💡관련 자료구조: 배열

---

검색

저장되어 있는 자료 중에서 원하는 항목을 찾는 작업
목적하는 탐색 키를 가진 항목을 찾는 것

검색의 종류

순차검색
이진검색
인덱싱 (DB와 밀접)

이진검색

자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법이다. 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다.
따라서 자료에 삽입이나 삭제가 발생했을 때 배열의 상태를 항상 정렬 상태로 유지하는 추가 작업이 필요하다.

검색 과정

1. 자료의 중앙에 있는 원소를 고른다.
   👉배열의 크기가 홀수인 경우, 중앙 원소의 인덱스는 (첫 인덱스 + 끝 인덱스)/2
2. 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다.
3. 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행한다.
4. 찾고자 하는 값을 찾을 때까지 1~3번의 과정을 반복한다.
   👉이때 자료의 오른쪽 반으로 이동했다면, '첫 인덱스'는 '중앙 인덱스+1' 로 바뀌어야 한다.
   👉혹은 자료의 왼쪽 반으로 이동했다면, '마지막 인덱스'는 '중앙 인덱스-1' 로 바뀌어야 한다.
5. 중앙 인덱스가 가리키는 값과 현재 찾고자 하는 값이 일치하면 검색을 완료한 것이다.
6. 첫 인덱스와 끝 인덱스가 교차되는 순간에는 찾고자 하는 값이 현재 자료에는 없는 것이다. (강의: 이진검색 11:18)

구현 | 반복문

public class Search {

	static int[] arr = {2, 5, 10, 15, 23, 30, 35};
	static int len = arr.length;

	public static void main(String[] args) {
		
		System.out.println(binarySearch(28));
		
	} //main

	// boolean 반환: 해당 찾고자 하는 숫자가 있는지 없는지 체크
    // int 반환: 해당 숫자가 있는 인덱스 반환
	static int binarySearch(int key) {
		int start = 0;
		int end = len - 1;
		int mid;
		while(start <= end) {
			mid = (start + end)/2;
			if(arr[mid] == key) { //검색 성공
				return mid;
			} else if(arr[mid] > key) { //왼쪽 
				end = mid - 1;
			} else { //오른쪽
				start = mid + 1;
			}
		}
		// 📌start와 end가 뒤집히는 순간 검색 실패
        // 	 (start > end) 일 때
		return -1;
	}
} //end class

구현 | 재귀함수

public class 이진검색_재귀 {

	public static void main(String[] args) {
		int[] arr = { 8, 9, 17, 21, 23, 35, 88, 369 };
		
		System.out.println(binarySearch(arr, 21, 0, arr.length-1));
	}

	// boolean 반환 : 해당 찾고자 하는 숫자가 있는지 없는지 체크
	// int 반환 : 해당 숫자가 있는 인덱스 반환
	static boolean binarySearch(int[] arr, int key, int left, int right) {
		if(left> right) return false; // 검색 실패
		
		int mid = (left+right)/2;
		
		if(arr[mid] == key) return true;
		else if(arr[mid] > key)
			return binarySearch(arr, key, left, mid-1);
		else
			return binarySearch(arr, key, mid+1, right);
	}
}

이진검색 API

import java.util.Arrays;

public class 이진검색_API {

	public static void main(String[] args) {
		int[] arr = { 8, 9, 17, 21, 23, 35, 88, 369 };
        
		//찾았을 때는 해당 인덱스 반환
        // 못 찾았을 때는?
		System.out.println(Arrays.binarySearch(arr, 10));
	}
}