部分图文参考于：代码随想录 - 二分查找，本文仅作为个人学习使用，如有侵权，请联系删除。

1.概念

二分查找也称折半查找（Binary Search），是一种在有序数组中查找某一特定元素的搜索算法。我们可以从定义可知，运用二分搜索的前提是数组必须是有序的，这里需要注意的是，我们的输入不一定是数组，也可以是数组中某一区间的起始位置和终止位置。

2.注意点

● 二分查找的基础条件：数组是有序数组。二分查找的循环中，坚持循环不变量的原则。
● while中left与right之间的比较： <= 还是 <？
● 不同写法对应了right移动时的不同位置：right = mid - 1;还是right = mid;？
● 防溢出：int mid = left + (right - left) / 2;等同于int mid = (left + right) / 2;

3.题目1★: 704.二分查找

3.1.注意点

二分查找前提：1.数组为有序数组。2.数组中无重复元素。
循环不变量规则：在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作。

3.2.思路

将给定的target值与数组中间位置的元素比较：
● 如果相等，则查找成功，返回元素所在的位置。
● 如果不等，则需要查找的元素在中间元素以外的前半部分或是后半部分。
在缩小的范围内，以相同的方式进行查找，如此反复，直到找到为止；或是确定数组中没有所需查找到元素，查找不成功，返回查找失败的信息。
根据边界条件的不同，主要分为[left, right]和[left, right)两种写法。

3.3.解法1：二分查找[left, right]

● while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=。
● if (nums[mid] > target) right 要赋值为 mid - 1，因为当前这个nums[mid]一定不是target，那么接下来要查找的左区间结束下标位置就是 mid - 1。
● 例如在数组：1,2,3,4,7,9,10中查找元素2，如图所示：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1; //[left, right]
        while (left <= right) { //左闭右闭区间 [left, right]
            int mid = left + (right - left) / 2; //等同于(left+right)/2，防溢出
            if (nums[mid] < target) { //向右查找 [mid + 1, right]
                left = mid + 1;
            }
            else if (nums[mid] > target) { //向左查找 [left, mid - 1]
                right = mid - 1;
            }
            else { //nums[mid] == target，返回mid
                return mid;
            }
        }
        return -1; //找不到便返回-1
    }
};

● 时间复杂度：\(O(logn)\)
● 空间复杂度：\(O(1)\)

3.4.解法2：二分查找[left, right)

● 区间为[left, right)时，while(left < right){}；因为当left与right相等的情况在区间[left, right)没有意义。
● target > nums[mid]，修改left为mid + 1，在右区间继续查找，所查找区间为[mid + 1, right)。target < nums[mid]，修改right为mid，在左区间继续查找，所查找的区间为[left, mid)，下一个查询区间不会比较nums[mid]。
● 在数组：1,2,3,4,7,9,10中查找元素2，如图所示：（注意和法一的区别）

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size(); //[left, right)
        while (left < right) { //左闭右开区间 [left, right)
            int mid = left + (right - left) / 2; //等同于(left+right)/2，防溢出
            if (nums[mid] < target) { //向右查找 [mid + 1, right)
                left = mid + 1;
            }
            else if (nums[mid] > target) { //向左查找 [left, mid)
                right = mid;
            }
            else { //nums[mid] == target，返回mid
                return mid;
            }
        }
        return -1; //找不到便返回-1
    }
};

● 时间复杂度：\(O(logn)\)
● 空间复杂度：\(O(1)\)

4.题目2：35.搜索插入位置

4.1.思路

元素插入的位置包括以下四种情况：
情况1：目标值与数组中某元素相同：nums = [1,3,5,6]，target = 5，插入位置为2。
情况2：目标值插入数组某个位置：nums = [1,3,5,6]，target = 2，插入位置为1。
情况3：目标值在所有元素之前：nums = [1,3,5,6]，target = 0，插入位置为0。
情况4：目标值在所有元素之后：nums = [1,3,5,6]，target = 7，插入位置为4。

4.2.解法1：暴力解法

查找数组中是否存在大于或等于目标值的元素，其位置相当于目标值应插入位置，若存在则返回当前元素位置。
若不存在，则表示所有数组元素的值都小于目标值，目标值应置于数组末尾。

class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
    //情况1、2、3
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] >= target) return i;
    }
    return nums.size(); //情况4
}
};

● 时间复杂度：\(O(n)\)
● 空间复杂度：\(O(1)\)

4.3.解法2：二分查找[left, right]

class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) { // [left, right]左闭右闭
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    // 分别处理如下四种情况
    // 目标值在数组所有元素之前 -1 + 1
    // 目标值等于数组中某一个元素  return mid;
    // 目标值插入数组中的位置 [left, right]，return  right + 1
    // 目标值在数组所有元素之后的情况 [left, right]， 因为是右闭区间，所以 return right + 1
    return right + 1;
}
};

● 时间复杂度：\(O(log n)\)
● 空间复杂度：\(O(1)\)

4.4.解法3：二分查找[left, right)

class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
    int left = 0, right = nums.size();
    while (left < right) { // [left, right)左闭右开
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid;
    }
    // 分别处理如下四种情况
    // 目标值在数组所有元素之前
    // 目标值等于数组中某一个元素  return mid;
    // 目标值插入数组中的位置 [left, right)，return  right
    // 目标值在数组所有元素之后的情况 [left, right)， 因为是右开区间，所以 return right
    return right;
}
};

● 时间复杂度：\(O(log n)\)
● 空间复杂度：\(O(1)\)

5.题目3★：34. 在排序数组中查找元素的第一个和最后一个位置

5.1.思路

1.target 在数组范围的右边或者左边。
示例：nums = [3, 4, 5]，target = 2 or target = 6，此时应该返回[-1, -1]。
2.target 在数组范围中，而数组中不存在target。
示例：nums = [3,6,7], target = 5，此时应该返回[-1, -1]。
3.target 在数组范围中，且数组中存在target。
示例：nums = [3,6,7], target为6，此时应该返回[1, 1]。

5.2.解法：二分查找[left, right)

class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
    int leftBorder = searchLeftBorder(nums, target);
    int rightBorder = searchRightBorder(nums, target);
    if (leftBorder == -1 || rightBorder == -1) return {-1,-1};
    else return {leftBorder, rightBorder};
}

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

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

● 时间复杂度：\(O(logn)\)，其中n为nums的长度。
● 空间复杂度：\(O(1)\)。

5.3.解法2：代码精简

class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
    int leftBorder = searchBorder(nums, target, true);
    int rightBorder = searchBorder(nums, target, false);
    if (leftBorder == -1 || rightBorder == -1) return {-1,-1};
    else return {leftBorder, rightBorder};
}

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

● 时间复杂度：\(O(logn)\)，其中n为nums的长度。
● 空间复杂度：\(O(1)\)。

6.题目4：69. x 的平方根

6.1.思路

6.2.解法1：二分查找[left, right]

class Solution {
public:
    int mySqrt(int x) {
        int left = 0, right = x;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if ((long long)mid * mid == x) return mid;
            else if ((long long)mid * mid < x) left = mid + 1;
            else right = mid - 1;
        }
        return right;
    }
};

● 时间复杂度：\(O(logx)\)。
● 空间复杂度：\(O(1)\)。

6.3.解法2：二分查找[left, right)

class Solution {
public:
    int mySqrt(int x) {
        if (x <= 1) return x;
        int left = 0, right = x;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if ((long long) mid * mid < x) left = mid + 1;
            else if ((long long) mid * mid > x) right = mid;
            else return mid;
        }
        return left - 1;
    }
};

● 时间复杂度：\(O(logx)\)。
● 空间复杂度：\(O(1)\)。

7.题目5：367.有效的完全平方数

7.1.思路

7.2.解法1：二分查找[left, right]

class Solution {
public:
    bool isPerfectSquare(int num) {
        int left = 1, right = num;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if ((long long) mid * mid == num) return true;
            else if ((long long) mid * mid < num) left = mid + 1;
            else right = mid - 1;
        }
        return false;
    }
};

● 时间复杂度：\(O(log num)\)。
● 空间复杂度：\(O(1)\)。

7.3.解法2：二分查找[left, right)

class Solution {
public:
    bool isPerfectSquare(int num) {
        if (num == 1) return true;
        int left = 1, right = num;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if ((long long) mid * mid == num) return true;
            else if ((long long) mid * mid < num) left = mid + 1;
            else right = mid;
        }
        return false;
    }
};

● 时间复杂度：\(O(log num)\)。
● 空间复杂度：\(O(1)\)。