이진 검색

- 가운데에 있는 값과 찾는 키를 비교하고 다음 구간을 결정하고, 그 구간을 또 반으로 나누어 키 비교를 반복하는 검색방법을 통해 원하는 키를 찾는 것

- 이진 검색을 하기 위한 수행 조건은 정렬된 상태

- 시간복잡도 : log2의 N승

- 이진검색은 문제를 풀 때 이진검색의 아이디어를 접목하여 사용하기 때문에 스스로 구현할 줄 알아야함!

package com.ssafy.w0817;

import java.util.Arrays;

public class BinarySearchTest {

	public static void main(String[] args) {

		int[] arr = {10,4,6,20,35,7};
		Arrays.sort(arr); // 값들을 오름차순 정렬
		// 4,6,7,10,20,35
		System.out.println(binarySearch(arr, 6));
		System.out.println(binarySearch(arr, 35));
		System.out.println(binarySearch(arr, 50));
		
		System.out.println(Arrays.binarySearch(arr, 6));
		System.out.println(Arrays.binarySearch(arr, 35));
		System.out.println(Arrays.binarySearch(arr, 50));
	}
	
	// key에 해당하는 원소의 인덱스 리턴.
	static int binarySearch(int[] arr, int key) {
		int start = 0, end = arr.length-1;
		
		while(start<=end) {
			int mid = (start+end)/2; // 중간 위치
			if(arr[mid] == key) {
				return mid;
			}else if(arr[mid]<key) {
				start = mid+1;
			}else {
				end = mid-1;
			}
		}
		// 못찾았다면
		return -1;
	}

}

output

1
5
-1
1
5
-7