[Algorithm] Binary Search (이진탐색)

1. Binary Search (이진탐색)

 

이미 정렬되어 있는 배열에서 원하는 값을 찾을 때 사용하는 탐색 방법이다. 탐색 대상이 되는 리스트의 중간값을 기준으로 반으로 나눠 반복적으로 탐색을 진행한다.

 

찾고자 하는 타겟값이 중간값보다 작은 경우에는 왼쪽 리스트를 중간값보다 큰 경우에는 오른쪽 리스트를 탐색 대상으로 반복 탐색을 진행한다. 만약 타겟값과 중간값이 일치하는 경우 해당 위치를 반환하면 된다. 만약에 반복을 계속해서 서브 리스트의 크기가 0일 때까지 반복한다.

 

 

2. Binary Search 구현

 

import java.util.Arrays;

import Algorithm.Search.Search;

public class BinarySearch implements Search {

    private int N;

    private int[] nums;

    public BinarySearch(int[] nums) {
        N = nums.length;
        this.nums = Arrays.copyOf(nums, N);
    }

    @Override
    public int search(int val) {
        // 초기 배열의 탐색 대상 범위를 0 ~ N 으로 설정한다.
        int left = 0, right = N;

        // 탐색 대상 범위의 크기가 0이 될때까지 반복한다.
        while(left < right) {
            // 대상 범위의 중간값을 구한다.
            int mid = (left + right) / 2;

            // 중간값과 타겟값이 같은 경우 해당 값의 인덱스를 반환한다.
            if(nums[mid] == val) {
                return mid;

            // 타겟값이 중간값보다 큰 경우 중간값의 오른쪽 부분 배열을 대상으로 탐색을 진행한다.
            } else if(nums[mid] < val) {
                left = mid + 1;

            // 타겟값이 중간값보다 작은 경우 중간값의 왼쪽 부분 배열을 대상으로 탐색을 진행한다.
            } else {
                right = mid;
            }
        }
        // 타겟값이 없는 경우 -1을 반환한다.
        return -1;
    }
    
}

- source code: https://github.com/rmk1075/CS/blob/main/Algorithm/Search/BinarySearch/BinarySearch.java

 

 

3. Binary Search 복잡도

- 시간 복잡도: O(log N)

• 탐색 대상의 범위가 계속해서 반으로 나눠지기 때문에 최종적으로 N개의 수에 1/2를 k 만큼 곱한 값이 1이 될 때까지 반복하게 된다.
• 이때 k의 값은 log N에 수렴하게 된다.

 

 

[reference]

- https://www.geeksforgeeks.org/binary-search/

Binary Search - GeeksforGeeks