바이너리 서치 알고리즘이란

바이너리 서치 알고리즘 Binary Search Algorithm

Definition

데이터 스트럭쳐에 담긴 아이템을 찾는 알고리즘 중 하나

1. 중심점을 찾아서 찾는 아이템과 비교한다.
2. 중심점보다 찾는 아이템이 크다면, 정렬이 되어 있으므로, 오른쪽에 아이템이 있다.
3. 오른쪽에서 다시 중점을 찾는다.
4. 찾는 아이템을 찾을때까지 반복한다.

• array가 정렬되어 있어야 사용할수 있다.
• 데이터를 새로 추가할때마다, 재정렬을 해야 한다.
• 아이템 추가보다 찾기를 많이 할때, 사용해야 한다.
• 분할 정복 기법 divide-and-conquer technique 중 하나이다.

Time complexity

O(log n)

Example

아래 예제는 루커젼을 이용한 것이다.
루커젼을 이용하지 않고 바이너리 서치를 할 수도 있다.

import java.util.NoSuchElementException;

public class Main {

    public static void main(String[] args) {

        int[] inputList = {1, 9, 44, 55, 88};
        int value = 55;

        System.out.println(getIndexValueArr(inputList, value));

    }

    private static int getIndexValueArr(int[] input, int value) {
        return binarySearchRecur(input, 0, input.length - 1, value);

    }

    private static int binarySearchRecur(int[] input,
                                         int mostLeft,
                                         int mostRight,
                                         int value) {
        if (mostRight < mostLeft) { /*value not found*/
            throw new NoSuchElementException();
        }

        int mid = mostLeft + ((mostRight - mostLeft) / 2);

        if (input[mid] == value) { /*found the value*/
            return mid;
        } else if (input[mid] > value) { /*value is left side*/
            return binarySearchRecur(input, mostLeft, mid - 1, value);
        } else { /*value is right side*/
            return binarySearchRecur(input, mid + 1, mostRight, value);
        }
    }
}

Explanation

step 1

step 2

step 3

step 4

step 5

step 6

step 7