이분 탐색 - Binary Search

이분 탐색 이란

• 탐색 범위를 두 부분으로 분할 하면서 찾는 방식
• 처음부터 마지막까지 돌면서 탐색하는 것 보다 훨씬 빠른 장점이 있다.

시간의 복잡도

• 전체 탐색 : O(N)
• 이분 탐색 : O(logN)

진행 순서

• 데이터를 정렬해야 한다.
• 시작 값인 start, 끝 값인 end로 중간 값인 mid 를 설정해야한다.
• mid값과 내가 구하고 싶은 값을 비교한다.
• 구할 값이 mid보다 높으면 start = mid + 1
• 구할 값이 mid보다 낮으면 end = mid-1
• 이 것을 start>=end가 될 때 까지 반복한다.

Code

public static int solution(int[] arr, int M) { // arr 배열에서 M을 탐색
	
    Arrays.sort(arr); // 정렬
	
    int start = 0;
    int end = arr.length - 1;
    int mid = 0;

    while (start <= end) {
        mid = (start + end) / 2; // start와 end로 mid 설정
        if (M == arr[mid]) {
            return mid;
        }else if (arr[mid] < M) {
            start = mid + 1;
        }else if (M < arr[mid]) {
            end = mid - 1;
        }
    }
    throw new NoSuchElementException("타겟 존재하지 않음");
}