BinarySearch에 대해서

* BinarySearch

 

 - 업/다운 게임과 유사하게, 찾는값 target을 기준으로 현재 탐색값이 target보다 작으면 up.

반대로 현재 탐색값이 target보다 크면 down을 함으로서 값의 범위를 좁혀나가는 것.

 

private int binarySearch(int target) {
    int left = 0;
    int right = arr.length-1;
    
    while(left<=right) {
    	int mid = (left+right)/2;
        if(target == arr[mid]) {
            return mid;
        }
        if(target < arr[mid])
            right = mid - 1;
        else
            left = mid + 1;
    }
    return -1;
}

 

- left는 제일 왼쪽, right는 탐색 해야 할 배열 길이의 -1을 초기화 한다.

- while 순환문의 조건을 작성할때 하나의 숫자가 남았을때 확인을 위하여, = 등호를 꼭 작성할 것.

- mid 의미 그대로 left와 right의 값을 절반으로 나눔.

- 첫 번째로 찾는 값이 나오면 현재 mid(idx)를 반환함.

- target이 현재 탐색값보다 작으면 mid를 기준으로 -1 값을 right에 갱신.

- target이 현재 탐색값보다 크면 mid를 기준으로 +1 값을 left에 갱신.

- while 순환을 다 했음에도 발견되지 않았으면 -1 반환.

 

* Lower bound, Upper bound.

 

 - 만약에 내가 찾는 값 target이 배열에 여러 개 있다면, 이진탐색을 돌렸을 때 어떤 위치가 나오게 될지는 아무도 모름. 이런 경우 위 2가지 개념을 사용함.

- Lower bound - 찾는값이 여러개 있을때 그중 인덱스가 가장 작은 값.

- Upper bound - 찾는값이 여러개 있을때 그중 인덱스가 큰값의 + 1.

- 코드레벨에서 구현의 차이는 target과 현재 탐색값의 등호의 유무이다. 아래 참고.

 

private int upperBound(int target) {
    int left = 0;
    int right = arr.length-1;
    int maxIdx = 0;
    
    while(left<=right) {
    	int mid = (left+right)/2;
        if(target<arr[mid]) {
            right = mid - 1;
            maxIdx = Math.min(maxIdx, mid);
        }
        else {
            left = mid + 1;
        }
    }
    return maxIdx;
}

 

- 코드는 기존의 binarySearch() 함수와 유사함.

- 차이점은 maxIdx를 한개 더 생성해서 target값 보다 +1인 Idx를 반환한다는 것.

- target < arr[mid]를 통해서 right 를 조정함.

- lower Bound는 위 조건식에서 = 붙여주면 끝.