[알고리즘] BinarySearch # lowerBound / upperBound

* 탐색 전 꼭꼭 int[] arr 정렬하기 !!

 

> BinarySearch

public static int(int[] arr, key){
	int start = 0;
    int end = arr.size();
    
    while(start < end){
    	int mid = (start + end) / 2;
        if(arr[mid] == key){ // 구하고자 하는 값을 찾음
        	return mid;
        }else if(arr[mid] < key){ 
        	start = mid + 1; 
        }else{
        	end = mid - 1;
        }
    }
    return -1; // 탐색 실패
}

 

> lowerBound 이상의 값 찾기!

public static int lowerBound(int[] arr, key){
	int start = 0;
    int end = arr.size();
    
    while(start<end){
    	int mid = (start + end)/2;
        if(arr[mid] < key){
        	start = mid + 1;
        }else{
        	end = mid;
        }
    }
    return start;
}

 

> upperBound 이하의 값 찾기!

public static int lowerBound(int[] arr, key){
	int start = 0;
    int end = arr.size();
    
    while(start<end){
    	int mid = (start + end)/2;
        if(arr[mid] <= key){
        	start = mid + 1;
        }else{
        	end = mid;
        }
    }
    return start;
}

 

> 관련문제

10816 숫자 카드 2 https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2