[JAVA] 배열 - Binary search (이분 탐색)

배열을 다시 공부하며 라이브러리의 메소드를 사용하지 않고 binary search를 직접 구현 해보고자 한다.

 

순차적 순회(for문으로 인덱스 0부터 if로 찾아보는 것)는 최악의 경우 N의 시간 복잡도를 가진다

 

그에 반해 binary search는 인덱스를 반씩 나눠가면서 찾고자 하는 수를 찾기 때문에 logN의 시간 복잡도를 가진다.
(못찾으면 인덱스를 반으로 숭당 잘라서 그부분만 다시 순회해서 if로 찾으면 된다)

 

낮은 인덱스 : 0 

높은 인덱스 : 찾아야하는 배열의 길이

 

중간 인덱스 (핵심!!) : (낮은 인덱스 + 높은 인덱스) / 2

 

이렇게 구한 중간 인덱스를 통해 찾고자하는 수를 찾으면 순회끝! 

 

아래 코드를 보면 더 명확하게 알 수 있다.

 

public static Integer binarysearch(Integer[] integers,int findValue){
    int low = 0;
    int high = integers.length-1;

    while (low <= high) {
        int mid = (low + high) / 2;
        int comp = integers[mid];
        if (findValue == comp) {
            return mid;
        } else if (findValue > comp) {
            low = mid+1;
        }else{
            high = mid -1 ;
        }
    }
    throw new IllegalArgumentException("Array doesn't have findValue");
}

 

하면서 계속 오류가 났던 부분이 low와 high가 같아 지는 경우가 생겼는데 그것을 빼놓고 while의 조건문을 low < high로 놓고 테스트를 해서 while이 종료가 되었다. 

 

제대로 만들었는지 Arrays의 binarySearch 메소드와 비교했더니 아주 잘 동작하였다.

(테스트 코드는 아래에 기재해두겠다.)

 

<테스트 코드>

import java.util.Arrays;
import java.util.Random;

public class BinarySearchTest {
    public static void main(String[] args) {

        int n=100;
        for (int a = 0; a < 20; a++) {
            Integer[] integers = new Integer[n];

            Random random = new Random();
            for (int i = 0; i < n; i++) {
                integers[i] = random.nextInt(n);
            }
            Arrays.sort(integers);

            int idx = random.nextInt(n);
            int findValue = integers[idx];

            System.out.println("  findValue : " +findValue + "   idx : " + idx);

            long start = System.currentTimeMillis();


            int search = 0;
            try {
                search = BinarySearch.binarysearch(integers, findValue);
            } catch (Exception e) {
                System.out.println("e = " + e);
            }
            long end = System.currentTimeMillis();

            System.out.println("search = " + search + "\t time : " + (end-start));

            start = System.currentTimeMillis();
            int method = Arrays.binarySearch(integers, findValue);
            end = System.currentTimeMillis();

            System.out.println("method = " + method + "\t time : " + (end-start));
            System.out.println();
        }
    }
}