[Algorithm] 이분 탐색/이진 탐색(Binary Search)

Idea

• 이진 탐색(이분 탐색)은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
• 이진 탐색을 사용할 때는 반드시 배열 내부의 데이터가 정렬되어 있어야 한다.
• (left, mid, right)를 사용하며 찾아야 하는 수의 범위 중 가운데의 값과 찾고자 하는 값을 비교하여 대소관계에 따라 특정 구간으로 이동하는 것을 반복한다.

• 범위 속의 원소의 개수가 1개가 될 때까지 계속 탐색을 진행해야 하므로 while문을 통해 (left <= right)의 조건을 걸고, 이후, 중간에 위차한 값의 대소 관계에 따라 left와 right의 값이 바뀌며 진행된다.
• 영상의 Binary search(이분 탐색)과 Sequential search(순차 탐색)의 비교 횟수를 보면 이분 탐색의 탐색 횟수가 훨씬 적은 것을 확인할 수 있다.

Code

public class BinarySearch {
	
    // 반복문 이용
    public static int binarySearchIterative(int[] arr, int number) {
        int left = 0;
        int right = arr.length - 1;

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

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

        return -1; // 요소를 찾지 못한 경우
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59};  // 정렬되어야 함
        int number = 5;  // 찾으려는 수

        int result = binarySearchIterative(arr, number);

        if (result != -1) {
            System.out.println("결과는 : " + result);
        } else {
            System.out.println("찾지 못함.");
        }
    }
}

Time Complexity

이분 탐색의 시간복잡도는 O(log N)이다. 원하는 수를 찾을 때까지 탐색을 할 때마다 탐색 범위가 절반씩 줄어든다. 따라서 탐색 범위는 N, N/2, N/4, ..., 1 이 된다.

 

처음부터 끝까지 원하는 값을 찾기 위해 순서대로 탐색하는 순차 탐색의 시간복잡도는 O(N)인데 이분탐색은 탐색 대상을 절반식 줄여 나가기 때문에 탐색 횟수가 크게 적다.