[Core] Binary Search

이진탐색 방법

top boundary 찾을 때

int low = 1, high = N, mid;
int A[N];
int M, ans;
while (low <= high)
{
    mid = (low+high)/2;

    if (A[mid] >= M){
        high = mid - 1;
        ans = mid;
    }else if (A[mid] < M) {
        low = mid + 1;
    }
    //else break;
}

Bottom boundary 찾을 때

int low = 1, high = N, mid;
int A[N];
int M, ans;
while (low <= high)
{
    mid = (low+high)/2;

    if (A[mid] > M){
        high = mid - 1;
    }else if (A[mid] <= M) {
        low = mid + 1;
        ans = mid;
    }
    //else break;
}

특정값을 찾을 때

int low = 1, high = N, mid;
int A[N];
int M, ans;
while (low <= high)
{
    mid = (low+high)/2;

    if (A[mid] > M){ 
        high = mid - 1;
    }else if (A[mid] < M) {
        low = mid + 1;
    }
    else break;
}
if (low <= high) mid;
else //못찾음

public class BinarySearcher {         public int search(int[] arr, int target) {                 int first = 0;                 int last = arr.length;                 int mid;                 while (first <= last) {                         mid = (first + last) / 2;                         if (target == arr[mid]) {                                 return mid;                         }                         else {                                 if (target < arr[mid])                                                last = mid - 1;                                 else                                         first = mid + 1;                         }                         // if target is not existed,                         // not occur reversal of the first and last                 }                                  return -1;                 // when target is not existed         } }