date: 2020/02/01

基本概念

二分查找算法细节详解 

前提:有序

二分查找的思路非常简单,但细节比较头疼——什么时候该取等号?什么时候该加减一?

可以分为三种:

查找一个值

(不考虑重复值)

查找左边界

(一系列重复值的最左侧元素)

查找右边界

(一系列重复值的最右侧元素)

left = 0

right = nums.size() - 1

right = nums.size()

while(left <= right)

while(left < right)

left = mid + 1

right = mid - 1

right = mid

找到即结束

找到后继续收缩右边界

找到后继续收缩左边界

if(nums[mid] == target)

    return mid

if(left < nums.size())

    if(nums[left] == target)

        return left

left--;

if(left >= 0)

    if(nums[left] == target)

        return left


704二分查找(简单)

https://leetcode-cn.com/problems/binary-search

最简单的一种——查找一个值

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


034在排序数组中查找元素的第一个和最后一个位置(中等)

https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array

二分查找的边界搜索问题,包括左边界和右边界,

这道题可以明显地看出搜索左边界和搜索右边界地异同

int searchEdge(vector<int>& nums, int target, bool left_edge){
    int left = 0, right = nums.size();
    while(left < right){
        int mid = (left + right) / 2;
        if(left_edge){
            if(nums[mid] >= target){
                right = mid;
            }else{  // nums[mid] < target
                left = mid + 1;
            }
        }else{
            if(nums[mid] > target){
                right = mid;
            }else{  // nums[mid] <= target
                left = mid + 1;
            }
        }
    }
    
    if(left_edge){
        if(left < nums.size() && nums[left] == target)
            return left;
    }else{
        left--;
        if(left >= 0 && nums[left] == target)
            return left;
    }
    return -1;
}

vector<int> searchRange(vector<int>& nums, int target) {
    if(nums.size() == 0) return vector<int>(2, -1);
    int left = searchEdge(nums, target, true);
    if(left == -1) return vector<int>(2, -1);
    int right = searchEdge(nums, target, false);
    vector<int> result = {left, right};
    return result;
}


069x的平方根(简单)

https://leetcode-cn.com/problems/sqrtx

 也即 对于一个大于等于4的数,其平方根小于等于它的一半

而且显而易见,如果平方根结果取整, 而 

需要查找满足条件的最大正数a

二分查找一个值的变种,以查找为目标,

如果恰好没有这样的,那么退出循环时会得到,这时就是答案

int mySqrt(int x) {
    if(x == 0)  return 0;
    if(x <= 3)  return 1;
    long left = 2, right = x / 2;
    while(left <= right){
        long mid = (left + right) / 2;
        long square = mid * mid;
        if(square == x){
            return mid;
        }else if(square > x){
            right = mid - 1;
        }else{  // square < x
            left = mid + 1;
        }
    }
    return right;  // 必须返回right而不是left
}

image.png

本题迭代公式:

// 结束条件1:变化量足够小
int mySqrt(int x) {
    if(x == 0) return 0;
    double cur = 1.0, pre;
    do{
        pre = cur;
        cur = (cur + x / cur) / 2;
    }while(fabs(cur - pre) > 1e-6);
    return cur;
}

// 结束条件2:直接判断 a^2 <= x < (a+1)^2
int mySqrt(int x) {
    if(x == 0) return 0;
    double cur = 1.0, pre;
    long curf;
    do{
        pre = cur;
        curf = cur = (cur + x / cur) / 2;
    }while(curf*curf > x || (curf+1)*(curf+1) <= x);
    return curf;
}


367有效的完全平方根(简单)

https://leetcode-cn.com/problems/valid-perfect-square

069x的平方根 的简化版