이분 탐색

//구현
static public void binarySearch(int lo,int hi,int num){
	while(lo<=hi){
    	mid = (hi-lo)/2;
        if(mid==num) return true;
        if(num>mid) lo=mid+1;
        if(num<mid) hi=mid-1;
    }
    return false;
}
//콜렉션
int idx = Collections.binarySearch(list,num);
/*
	찾으면 인덱스 리텅
    못찾으면 (들어가야 할 위치 +1) *-1
*/

 

left-> 내가 첫등장, 나보다 작은거 관심 없다.

right -> 내가 마지막 등장, 나보다 같거나 작은거 관심없다!

 

근데 target<num 일때는 전부 hi=mid 해야한다 -> mid가 더 클때도 예상 해야하기 때문

 

기본 서치  => lo,hi 모두 탐색 범위, hi=arr.length-1 : lo=hi되도 mid 움직이고 검사한 뒤 판단(mid로 값 판단 하기 때문)

idx 서치  => [lo, hi) , hi=arr.length  : lo=hi 되는 순간 그게 정답 (값 범위 전용)

 

이래서 종료 조건이 다르다