2.02_二分搜索

查找v在有序数组中的位置

假设在[begin,end)范围内搜索某个元素v，mid == （begin + end）/2
如果 v < mid ,去 [begin,mid) 范围内二分搜索
如果 v > mid ,如 [mid+1,end)范围内二分搜索
如果 v == mid , 直接返回mid

int search(int *arr,int length,int v)
{
    int begin = 0;
    int end = length;
    while (begin < end) {
        int mid = (begin + end) >> 1;
        if (v < arr[mid]) {
            end = mid;
        }else if(v > arr[mid]){
            begin = mid + 1;
        }else{
            return mid;
        }
    }
    return - 1;
}

查找v在有序数组中的插入位置

int search2(int *arr,int length,int v)
{
    int begin = 0;
    int end = length;
    while (begin < end) {
        int mid = (begin + end) >> 1;
        if (v < arr[mid]) {
            end = mid;
        }else{
            begin = mid + 1;
        }
    }
    return begin;
}