Binary Search

 

Binary Search의 개념

이번엔 Binary Searcc에 대해서 공부해보겠습니다. 쉽게 말해 업/다운 게임을 생각하시면 될것같습니다

업다운 게임은 한사람이 수를 생각하여 그 수를 맞추기위해서 예측한 수보다 큰지 작은지 업/다운을 외치시면됩니다 

이진탐색또한 똑같습니다. 가운데의 값을 찾고자 값을 비교하여 대소관계에따라 특정 구간으로 이동하는것을 반복합니다.

 

업/다운 게임

 

찾는 범위가 나올때까지 우리는 계속 값을 찾아내야합니다.

 

쉽게생각하여 while(true)을 넣어서 if(예측한 수 == target 수 )일때 종료하면됩니다 

수를 업/다운 하기위해선 저는 아마 정렬을 사용할것같습니다. 이때 시간복잡도를 생각하여 logN이 낫지않을까요? ㅎㅎ 

그렇게된다면 left는 1번째를 가리키고, right는 오른쪽 맨끝을 가리키게됩니다. 그리고나서 제가 부른 숫자가 target보다 작다면 left 범위를 줄여주고, 제가 부른숫자가 target보다 크다면 right 를 높이면됩니다

1 2 3 4 5 6 7 8 9 10 이라 가정한다면 left는 1, right는 10입니다. target은 3이라면 제가 6을 골랐을때  다시 1,2,3,4,5,6에서 무조건 답이 나온다고 생각하시면 편할것같습니다. 

결국, 내가 고른 숫자보다 target이 크다면 내가 고른숫자부터 right까지 무조건 답이 존재하기때문에 내가 고른숫자가 곧 left가 됩니다. 즉 left+1부터 시작한다면 답이 존재하겠죠? 반대로 target보다 작다면 left부터 임의로 고른 숫자안에 답이 존재하기때문에 right-1부터 시작하는것입니다. 

 

int left = 0, right = n - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if(arr[mid] == target) { // 찾았다면 해당 index를 반환합니다.
                idx = mid;
                break;
            }
            
            if(arr[mid] > target) // 찾으려는 숫자가 더 작다면
                right = mid - 1;  // 왼쪽 구간으로 이동해야 합니다.
            else                  // 찾으려는 숫자가 더 크다면
                left = mid + 1;   // 오른쪽 구간으로 이동해야 합니다.
        }

이것이 Binary Search입니다. 

 

Lower Bound

그렇다면 내가 원하는 target이 배열에 여러개있다면 어떻게 해야할까요?

 

내가 찾고싶은 target값은 3이지만

 

1,2,3,3,3,3,3,4,5 인 배열이라면 어떤위치의 값을 꺼내야할까요? 결국 아무도 모릅니다. 그렇게해서 나온 방법이 Lower Bound입니다. 

 

 

Lower Bound는 원하는 값  target 이상이 처음으로 나오는 위치입니다. 결국 바꿔말해서 target보다 같거나 큰  원소의 위치들 중 가장 작은 값을 출력해야합니다. 이 값을 구하기위해선 하나의 변수를 이용해야합니다 minIdx를 이용하여 가장 작은값을 출력해야합니다. 이때 minIdx는 언제 갱신 해야하는지를 잘생각해야합니다. 

저라면은.... 아마 target을 찾고 난뒤 index를 계속 최소값으로 정의할것같습니다. 즉 arr[mid]=target에서 끝나지않고 

arr[mid]>=target (내가고른 값이 target보다 크거나 같을때) minIdx= Math.min(mid,minIdx)로 갱신을 하는것이죠 

 

    int left = 0;                          // 첫 번째 원소의 위치로 설정합니다.
    int right = n - 1;                     // 마지막 원소의 위치로 설정합니다.
    int minIdx = n;                        // 최소이므로, 답이 될 수 있는 값보다 더 큰 값으로 설정합니다.
    while (left <= right) {                // [left, right]가 유효한 구간이면 계속 수행합니다.
        int mid = (left + right) / 2;      // 가운데 위치를 선택합니다.
        if(arr[mid] >= target) {           // 만약에 선택한 원소가 target보다 같거나 크다면 
            right = mid - 1;               // 왼쪽에 조건을 만족하는 숫자가 더 있을 가능성 때문에 right를 바꿔줍니다.
            minIdx = Math.min(minIdx, mid);// 같거나 큰 값들의 위치 중 최솟값을 계속 갱신해줍니다.
        }
        else                               
            left = mid + 1;                // 작은 경우라면 left를 바꿔줍니다.
    }

 

 

그렇다면 이제 중복된값의 최소 Index를 찾을수있게됩니다. 하지만  원하는 target값을 초과하는 값에서 최초로 나오는 위치를 얻고싶다면 어떻게해야할까요?

 

Upper Bound

예를 들어 1,2,3,3,3,3,3,3,4,5,6 인경우 3인 값을 초과하는 값은 4입니다. 이때 중복된 3인 값이 너무많아서 4을 출력하기 어렵겠죠? 이때 나온것인 Uppder Bound입니다 

 

 

이때는 정말 쉽습니다 arr[mid] >= target 인경우 mid의 최소값을 정했죠  하지만 arr[mid] > target인경우 arr[mid]보다 target값이 작을때  arr[mid]는 이미 target을 초과한 경우입니다. 이때 큰값들의위치로 이동하지만 mid의 index 위치를 최소값을 정한다면 ? 결국 우린 target값이 초과했을때의 나온 최초의 최소값을 얻게됩니다.

    int left = 0;                          // 첫 번째 원소의 위치로 설정합니다.
    int right = n - 1;                     // 마지막 원소의 위치로 설정합니다.
    int minIdx = n;                        // 최소이므로, 답이 될 수 있는 값보다 더 큰 값으로 설정합니다.
    while (left <= right) {                // [left, right]가 유효한 구간이면 계속 수행합니다.
        int mid = (left + right) / 2;      // 가운데 위치를 선택합니다.
        if(arr[mid] > target) {            // 만약에 선택한 원소가 target보다 크다면 
            right = mid - 1;               // 왼쪽에 조건을 만족하는 숫자가 더 있을 가능성 때문에 right를 바꿔줍니다.
            minIdx = Math.min(minIdx, mid);// 큰 값들의 위치 중 최솟값을 계속 갱신해줍니다.
        }
        else                               
            left = mid + 1;                // 같거나 작은 경우라면 left를 바꿔줍니다.
    }

 

lower bound와 uppder bound의 성질을 잘 이해 하시게됐다면 배열 내 데이터의 수는 두값이 차이이며, 데이터가 존재하지않는다면 두 값이 같음을 유추할수있게되는겁니다. 

 

Upper Bound - Lower Bound => 배열 내 수의 개수 

Lower Bound와 Upper Bound의 위치가 같으면 배열 내 값이 없다고 볼수있습니다. 

 

하나만 더 공부해보죠 ! 

그렇다면 우리는 

 

Other Question

Lower Bound이 존재하는 값들중 즉, 중복되는 값 들중 최고값의 Index를 구하고 싶으면 어떻게해야할까요?

 

이때는 maxIdx갓이 갱신되는 순간이 언제인지를 이해해야합니다. maxIdx값은 arr[mid]보다 같거나 작은경우에 대해서 mid값들중 최댓값이 되어야합니다. left값을 이동해줘야한다는 말인데요 이때 right값이 아닌경우는 right를 사용하게되면 내가 임의로 설정한 값보다 오른쪽 값들이 존재할수있기때문에 방지해줘야합니다. 

결국 arr[mid] <= target일때 최대 index를 가져야한다는거죠

 

   int left = 0;                          // 첫 번째 원소의 위치로 설정합니다.
    int right = n - 1;                     // 마지막 원소의 위치로 설정합니다.
    int maxIdx = -1;                       // 최대이므로, 답이 될 수 있는 값보다 더 작은 값으로 설정합니다.
    while (left <= right) {                // [left, right]가 유효한 구간이면 계속 수행합니다.
        int mid = (left + right) / 2;      // 가운데 위치를 선택합니다.
        if(arr[mid] <= target) {           // 만약에 선택한 원소가 target보다 같거나 작다면 
            left = mid + 1;                // 오른쪽에 조건을 만족하는 숫자가 더 있을 가능성 때문에 left를 바꿔줍니다.
            maxIdx = Math.max(maxIdx, mid);// 같거나 작은 값들의 위치 중 최댓값을 계속 갱신해줍니다.
        }
        else                               
            right = mid - 1;               // 값이 더 큰 경우라면 right를 바꿔줍니다.
    }

 

자 이렇게 기본적인 이진탐색 기본 개념이 끝났습니다. 다음은 다른 알고리즘으로 찾아뵙겠습니다.