이진 탐색 (Binary Search)

찾으려는 값과 데이터 중앙에 있는 값을 비교 -> 찾으려는 값이 더 작으면 데이터의 왼쪽부터, 찾으려는 값이 더 크면 데이터의 오른쪽부터 다시 이진 탐색을 반복해서 값을 찾는다
(데이터가 정렬되어있어야함)

시간 복잡도 : O(logn)

        // 이진 탐색
        int[] arr = {1, 2, 5, 10, 20, 30, 40, 50, 60};
        int left = 0;
        int right = arr.length - 1;
        int target = 30;
        int result = 0;

        // left와 right가 만날때까지
        while (left <= right) {
            // 중앙값
            int mid = (left + right) / 2;
            // 찾으려는 값과 중앙값이 같을 경우
            if (target == arr[mid]) {
                result = mid;
                break;
            } else if (target < arr[mid]) {
                // 찾으려는 값이 중앙값보다 작을 경우, 왼쪽에서 찾기
                // left : 맨 왼쪽, right : 중앙의 바로 옆
                right = mid - 1;
            } else {
                // 찾으려는 값이 중앙값보다 클 경우, 오른쪽에서 찾기
                left = mid + 1;
            }
        }
        System.out.println("result index = " + result);

        // java에서 제공되는 이진 탐색 : 해당 값의 위치를 반환함
        int[] arr = {1, 2, 5, 10, 20, 30, 40, 50, 60};
        System.out.println(Arrays.binarySearch(arr, 10)); // 3
        System.out.println(Arrays.binarySearch(arr, 6)); // -4

찾으려는 값이 배열에 없을 때, 찾으려는 값이 오름차순으로 원래 있었을 위치의 (6이라면, 5와 10 사이인 3번 인덱스)음수에서 -1한 값을 반환한다.