[Java code] 이진 탐색(Binary Search) - 선형 이하 시간(Sublinear Time) 알고리즘

100,000개의 순차적인 사진들 중에서 한 장의 사진을 찾고싶다면, 몇 장의 사진을 확인해야 할까?

 

50,000번 째의 사진을 확인하고 내가 찾는 사진이 그 이전인지 이후인지 알 수 있다면

계속 절반으로 나누니 밑이 2인 log를 사용하면 된다

(25,000 -> 12,500 -> ...)

 

따라서 확인해야 하는 사진의 장수는 대략 밑이 2인 logN이라고 할 수 있다

 

---

 

위의 알고리즘을 이진 탐색(binary search)라고 부르고 다음과 같이 정의할 수 있다

 

biSearch(A[], x) = 오름차순으로 정렬된 배열 A[]와 찾고 싶은 값 x가 주어질 때 A[i-1]<x<=A[i]인 i를 반환한다

이때 A[-1] = 음의 무한대, A[N] = 양의 무한대로 가정한다.

 

따라서 A[]에 x가 존재하는 경우 이 함수는 첫 번째 x의 위치를 반환하고, 없는 경우 x보다 큰 첫 번째 원소를 반환한다

(C++ 표준 라이브러리에는 그래서 이진 탐색 함수가 두 개 존재한다

x를 삽입할 수 있는 위치 중 가장 이른 것을 반환하는 lower_bound()와 가장 뒤의 것을 반환하는 upper_bound()가 있다)

 

코드는 다음과 같다

 

package com.company;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] arr1 = new int[] {1, 2, 3, 4, 5};
        System.out.println(biSearch(arr1, 4));
        //3
    }
    public static int biSearch(int[] arr, int x) {
        int n = arr.length;
        int lo = -1, hi = n, mid;

        while(lo < hi) {
            mid = (lo+hi)/2;
            if(arr[mid] < x)
                lo = mid+1;
            else
                hi = mid;
        }

        return hi;	//upper_bound()
    }
}