Search - binary search

Binary Search

이분 검색은 단순하게 이야기하자면 반띵해서 반날리고...반띵해서 반날리고..의 반복이다.

좀 더 자세하게 이야기하자면, 값이 정렬된 배열에서 중앙값을 찾아 해당 값이 찾고자 하는 값보다 큰지 작은지를 확인하고

작거나 크다면 그 앞 혹은 뒤로 반을 날려준다. 그 다음은 역시 반복한다.

다음은 간단하게 짜본 코드이다.

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

public class binarySearch {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int target = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

        solution(n, target, arr);
    }

    static void solution(int n, int target, int[] arr) {
        int answer = 0;

        Arrays.sort(arr);
        int lt = 0;
        int rt = n - 1;
        while(lt <= rt){
            int mid = (lt + rt) / 2;
            if(arr[mid] == target){
                answer = mid+1;
                break;
            }

            if(arr[mid] > target) rt = mid - 1;
            else lt = mid + 1;
        }

        System.out.println(answer);
    }
}

자 이걸 이제 머릿속에 우겨넣자.

맨날 까먹지만.