[Algorithm] Binary Search Algorithm

Binary Search Algorithm (이진 탐색 알고리즘)

 

이진 탐색 알고리즘은 탐색 알고리즘의 하나로 이미 정렬되어 있는 배열을 대상으로 원하는 값을 찾는 알고리즘이다.

 

정렬되어 있는 배열의 중간의 값과 타겟이 되는 값을 비교해서 탐색을 진행한다. 중간값과 타겟이 동일하다면 해당 값을 반환한다. 만약 타겟이 되는 값이 중간값보다 큰 경우 중간 값을 기준으로 우측, 작다면 중간 값을 기준으로 좌측의 부분 배열을 대상으로 반복적으로 탐색을 진행한다. 이때 대상이 되는 배열의 왼쪽 인덱스가 오른쪽 인덱스보다 크다면 값이 없는 것으로 판단하여 탐색을 중단한다.

 

위의 예제 이미지는 정렬되어있는 배열에서 타겟 값인 23을 탐색하려고 한다.

1. 첫번째 과정에서 중간값은 16 이다. 16은 타겟 값인 23 보다 작기 때문에 16을 기준으로 오른쪽에 있는 부분 배열을 대상으로 다음 과정을 진행한다.
2. 두번째 과정에서 중간 값은 56이 된다. 56은 23보다 크기 때문에 56을 기준으로 왼쪽 부분 배열을 대상으로 탐색을 진행한다.
3. 세번째 과정에서 중간 값은 타겟 값과 같은 23이기 때문에 해당 위치를 반환한다.

 

시간 복잡도

• 이진 탐색 방법은 중간값을 기준으로 배열을 반으로 나눠 반복적으로 탐색을 진행하게 된다.
• 이를 통해서 대상이 되는 리스트의 개수 N이 계속 2로 나뉘어 지게 되어서 시간복잡도는 O(log N)이 된다.

 

이진 탐색 방법 구현

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

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) {
        int left = 0, right = N;
        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;
            }
        }
        return -1;
    }
}