[알고리즘] 이진탐색

이진탐색 (Binary Search)

 

• 정렬된 상태의 데이터에서 특정 값을 탐색하는 방법
• 찾고자 하는 값과 데이터 중앙에 있는 값을 비교
• 찾고자 하는 값이 더 작으/크면 데이터 왼/오른쪽 부분에서 다시 이진탐색

 

 

1. 직접 구현하기

 

public int binarySearch(int arr[], int target) {
    int left = 0;
    int right = arr.length - 1;

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

        if (target == arr[mid]) {
            return mid;
        } else if (target < arr[mid]) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return -1;
}

 

 

2. Arrays.binarySearch 메서드

 

public static void main(String[] args) {
    int[] arr = {1, 2, 5, 10, 20, 30, 40, 50, 60};

    System.out.println("== 데이터가 있는 경우 ==");
    System.out.println(Arrays.binarySearch(arr, 1)); // 0
    System.out.println(Arrays.binarySearch(arr, 10)); // 3
    System.out.println(Arrays.binarySearch(arr, 30)); // 5


    System.out.println("== 데이터가 없는 경우 ==");
    System.out.println(Arrays.binarySearch(arr, 3)); // -3
    System.out.println(Arrays.binarySearch(arr, 11)); // -5
    System.out.println(Arrays.binarySearch(arr, 35)); // -7

}

• 데이터가 있는 경우는 해당 데이터가 있는 인덱스를 반환
• 데이터가 없는 경우는 [해당 데이터가 있을 경우의 위치] - 1을 반환