二分查找算法

基本二分查找

 // 朴素的二分查找
long int binarySearch_basic(vector<int>& numbers, int target){
    if(numbers.size() <= 0) return -1;
    long int start = 0, end = numbers.size()-1, mid = 0;
    while(start <= end){
        mid = start + (end - start) / 2;
        if(target == numbers[mid]) return mid;
        else if(target < numbers[mid]) end = mid-1;
        else start = mid+1;
    }
    return -1;
}

二分查找的时间复杂度是 $O(logn)$ ， 二分查找里的边界条件有不同的写法：

1，朴素的二分查找，当 while 循环的条件中是 start<=end 时，在[start, end] 的闭区间上查找。end = mid -1; start = mid+1; 它最后一个循环是start = mid = end.

使用场景：基于二分查找的题目很多，但基本很多情况都是给排序好的数组之类的进行查找。

leecode34 二分查找第一与最后位置

主要是避免mid计算得到的还是start的位置，然后满足条件 start还是取mid，一直死循环。

// test case vector<int> data = {0,1,1,1,1,3};
//二分查找第一个目标元素，左边界，data里的第一个1
int binarySearch_hz_left(vector<int>& numbers, int target){
    if(numbers.size() <= 0) return -1;
    int start = 0, end = numbers.size(), mid = 0;
    while (start != end) {
        mid = start + (end - start) / 2; //void always loop
        if (numbers[mid] >= target) {
            end = mid; // maybe ans, do not jump
        } else {
            start = mid+1;
        }
    }
    if (start == numbers.size()) return -1;
    return numbers[start] == target ? start : -1;
    // return start; //直接返回start可能为0(target=-1)，6(target=4), 5(target=3)
}

//二分查找最后一个目标元素，右边界, data里的最后一个1
// mid有可能是末尾1，start不应该跳过去，故start = mid； 但mid > target end肯定可以-1跳过去
// final step, 1(start) 2(end)
int binarySearch_hz_right(vector<int>& numbers, int target){
    if(numbers.size() <= 0) return -1;
    int start = 0, end = numbers.size()-1, mid = 0;
    while (start != end) {
        mid = (start + end + 1) / 2; //void always loop
        if (numbers[mid] <= target) {
            start = mid;
        } else {
            end = mid - 1;
        }
    }
    return numbers[start] == target ? start : -1;
    //return start; //直接返回start可能为0(target=-1)，5(target=4),4(target=3)
}

另外在leecode上看到的解析，做个小记录参考，主要还是用上面的写法吧，找右边界好记点。

int searchRange_left_bound(vector<int>& nums, int target){
    if (nums.size() == 0) {
        return -1;
    }
    int start=0, end=nums.size();
    while (start < end) {
        int mid = start + (end - start) / 2;
        if (nums[mid] >= target) end = mid;
        else start = mid + 1;
    }
    if (start == nums.size()) return -1; // target 比所有数都大
    return nums[start] == target ? start : -1;
    //return start;
}

int searchRange_right_bound(vector<int>& nums, int target) {
    if (nums.size() == 0) return -1;
    int start = 0, end = nums.size();
    
    while (start < end) {
        int mid = start + (end - start) / 2;
        if (nums[mid] <= target) {
            start = mid + 1;
        } else {
            end = mid;
        }
    }
    if (end == 0) return -1;
    return nums[end-1] == target ? (end-1) : -1;
    //return end-1;
}

在翻转的排序数组查找目标值

leecode100-33：假设按照升序排序的数组在预先未知的某个点上进行了旋转。搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引。

int search(vector<int>& nums, int target){
    if(nums.size() <= 0) return -1;
    int start = 0;
    int end = nums.size() - 1;
    while(start <= end){
        int mid = start + (end-start)/2;
        // find it
        if(nums[mid] == target) return mid;
        
        // left side is ASE
        if (nums[start] <= nums[mid]){
            if(nums[start] <= target && nums[mid] > target) end = mid;
            else start = mid+1;
        }
        else{
            // right ride is ASE
            if(nums[mid] < target && target< nums[start]) start = mid+1;
            else    end = mid;
        }
    }
    return -1;
}

SwordToOffer 二维数组的查找

书P47，每次选取数组的右上角元素，如果目标值较小，就逐渐往左下走。

// P47 题目s4，二维数组查找数字
bool find_num(int* matrix, int rows, int columns, int number){
    bool found = false;
    if (matrix != nullptr && rows>0 && columns>0) {
        int row = 0;
        int col = columns - 1;
        while (row < rows && col >=0) {
            if (matrix[row * columns + col] == number) {
                found = true;
                break;
            }
            else if (matrix[row * columns + col] > number) --col;
            else ++row;
        }
    }
    return found;
}

查找第一个不小于目标值数的位置

找第一个大于等于目标值的下标，如 {1,2,3,4,4,4,5,8} target=6, 则答案是数组里8的下标7。如果是4的话，答案是3。

//give a sort array, return the index of num which >= target
long int big_binarysearch(vector<int>& nums, int target){
    if(nums.size() <= 0) return -1;
    long int start = 0;
    long int end = nums.size() - 1;
    if(nums[start] > target) return 0;
    if(nums[end] < target) return -1;
    long int res = 0;
    while(start+1 < end){
        long int mid = start + (end-start)/2;
        if (nums[mid] >= target){
            end = mid;
            res = mid;
        }
        else{
            start = mid;
        }
    }
    res = nums[start] >= target? start:end;
    return res;
}