이진 탐색

배열 데이터가 정렬되어 있어야만 사용가능.
탐색 범위를 절반으로 줄여가면서 탐색하는 방식.
찾으려는 데이터와 중간 지점의 데이터를 지속적으로 비교하며 원하는 데이터를 찾는다.

매장의 n개의 상품 번호 중 고객이 찾는 m개의 상품 번호를 찾는 것을 이진탐색으로 구현.
고객이 찾는 상품 번호와 같은 번호가 매장에 있다면 yes 아니면 no를 출력.
n = 5
[4, 5, 6, 7, 2]

m = 3
[2, 9, 5]

package solution0913;

import java.util.Arrays;
import java.util.Scanner;

public class 이진탐색 {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n  = sc.nextInt();
		int[] nArr = new int[n];
		for(int i=0; i<n; i++) {
			nArr[i] = sc.nextInt();
		}
		
		Arrays.sort(nArr);
		
		int m  = sc.nextInt();
		int[] mArr = new int[m];
		for(int i=0; i<m; i++) {
			mArr[i] = sc.nextInt();
		}
		
		for(int i=0; i<m; i++) {
			int ans = binarySearch(nArr, mArr[i], 0, n-1);
			if(ans == -1) System.out.println("no");
			else System.out.println("yes");
		}
	}

	static int binarySearch(int[] arr, int result, int start, int end) {
		while(start <= end) {
			int mid = (start+end)/2;
			if(arr[mid] == result) return result;
			if(arr[mid] < result) start = mid+1;
			else if(arr[mid] > result) end = mid -1;
		}
		return -1;
	}
}

특정 데이터를 찾기위해 전체 데이터를 확인하는 정렬 알고리즘보다 데이터가 정렬되어있으면 빠르게 원하는 데이터를 찾을 수 있다.