[java] binary search (lower bound) 구현하기

이진탐색은 탐색 대상이 정렬되어있을때 효율적으로 원하는 값을 검색할 수 있는 알고리즘이다.

구현 자체도 어렵지 않을 뿐더러 약간의 변형을 통해 해당 값을 찾는 것 뿐만 아니라 해당 값보다 같거나 큰 값이 나오는 첫 위치(lower bound)도 구할 수 있다.

 

 

기본 이진 탐색

public int binarySearch(int[] arr, target){
	
    int low = 0;
    int high = arr.size-1;
    int mid = 0;
    
    while(low <= high){
    	mid = (low+high)/2;
        if(target == arr[mid]){
        	return mid;
        } else if(target < arr[mid) {
        	high = mid-1;
        } else {
        	low = mid+1;
        }
    }
    
    return -1;
}

주어진 정수 배열 전체에서 목표 값을 찾는 함수이다.

 

 

Lower Bound

public int lowerBound(int[] arr, int target){
	
    int low = 0;
    int high = arr.size;
    int mid = 0;
    
    while(low < high){
    	mid = (low+high)/2;
        if(target <= arr[mid]){
        	high = mid;
        } else {
        	low = mid+1;
        }
    }
    
    return low;
}

주어진 정수 배열에서 목표 값과 같거나 큰 값이 처음으로 나오는 위치를 반환하는 함수이다.

일반 이진 탐색에서 high를 size-1로 둔 것과 달리 lower bound에서는 목표값보다 큰 값이 없을 수도 있기 때문에 high를 size 값으로 둔다.

upper bound의 경우 위의 코드에서 target값과 arr[mid] 값이 같은 경우를 low = mid+1;로 처리되도록 if문을 변경하면 된다.