이진탐색(Binary Search)

정렬된 배열이나 리스트에서 값을 찾는데 사용되는 알고리즘입니다.
중간값을 기준으로 배열을 절반씩 나누어 값을 찾는 방식 입니다.
큰 데이터셋에서 값을 찾을때 유리합니다.
선형 탐색 보다 빠릅니다.
정렬하는 과정에서 시간이 걸릴 수 있고, 동적 배열, 리스트에서는 사용하기 어렵습니다.

선형탐색
정렬되지 않은 배열에서 사용가능 합니다.
순차적으로 값을 확인하며 값을 찾습니다.

시간 복잡도

best: O(1) - 중간값을 찾는경우
average: O(log N)
worst: O(log N)

• 배열을 절반씩 줄여 나가면서 값을 찾는 형태를 수식으로 표현하여 시간 복잡도는 아래와 같은 수식을 통해 간략하게 알아볼 수 있습니다.
  $\frac{N}{2}\times \frac{1}{2}\times \frac{1}{2}\times \frac{1}{2}...$ => $O(log_2N)$

동작 순서

1. 배열 정렬이 필요합니다.
2. 중간 값을 선택하여 찾는 값과 비교합니다.
3. 중간값이 크다면 왼쪽, 작다면 오른쪽에서 2번 과정을 반복합니다.

코드 구현

반복

    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (arr[mid] == target) {
                return mid; // 값을 찾음
            } else if (arr[mid] < target) {
                left = mid + 1; // 오른쪽 절반 탐색
            } else {
                right = mid - 1; // 왼쪽 절반 탐색
            }
        }
        
        return -1; // 값을 찾지 못함
    }

재귀

    public static int recursiveBinarySearch(int[] arr, int left, int right, int target) {
        if (left > right) {
            return -1; // 값을 찾지 못함
        }

        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid; // 값을 찾음
        } else if (arr[mid] < target) {
            return recursiveBinarySearch(arr, mid + 1, right, target); // 오른쪽 절반 탐색
        } else {
            return recursiveBinarySearch(arr, left, mid - 1, target); // 왼쪽 절반 탐색
        }
    }

Lower/Upper Bound

Lower Bound: 찾고자 하는 값보다 크거나 같은 값이 처음으로 나타나는 위치.
Upper Bound: 찾고자 하는 값보다 큰 값이 처음으로 나타나는 위치.

활용

배열 내 특정 값의 범위(개수)를 구할 수 있습니다. -> Upper Bound - Lower Bound

코드 구현

Lower Bound

 public static int lowerBound(int[] arr, int target) {
        int left = 0;
        int right = arr.length;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] < target) {
                left = mid + 1; // 왼쪽 부분이 아닌 오른쪽 절반을 탐색
            } else {
                right = mid; // 해당 값 이상일 경우, 범위를 줄여서 탐색
            }
        }
        return left; // lower bound를 반환
    }

Upper Bound

   public static int upperBound(int[] arr, int target) {
        int left = 0;
        int right = arr.length;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] <= target) {
                left = mid + 1; // target 값보다 작거나 같은 경우, 오른쪽 절반을 탐색
            } else {
                right = mid; // target 값보다 큰 경우, 범위를 줄여서 탐색
            }
        }
        return left; // upper bound를 반환
    }