二分查找算法

二分查找

class Solution 
{
public:
    int search(vector<int>& nums, int target) 
    {
        int left = 0, right = nums.size() - 1;
        while(left <= right) // 等于也要进入循环
        {
            int mid = left + (right - left) / 2; // 防止溢出
            if(nums[mid] < target) left = mid + 1;
            else if(nums[mid] > target) right = mid - 1;
            else return mid;
        }
        return -1;
    }
};

总结：

1. 能使用二分查找的前提是具有二段性，无论是否有序，重要的是有二段性
2. 判断循环的条件要注意，等于的时候也要进入循环，因为都是未知的，当left和right相等时，具体到一个数也要进循环判断
3. 在算mid时要防止溢出
4. 本题也是朴素二分查找的模板

while(left <= right) // 等于也要进入循环
{
   int mid = left + (right - left) / 2; // 防止溢出
   if(...) left = mid + 1;
   else if(...) right = mid - 1;
   else return ...;
}

5. …根据二段性来填写

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

class Solution 
{
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        if(nums.size() == 0) return {-1, -1};
        int left = 0, right = nums.size() - 1;
        int begin = 0; // 用于记录左端点
        // 找左端点
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        if(nums[left] != target) return {-1, -1};
        else begin = left;
        // 找右端点
        left = 0, right = nums.size() - 1; // 重置指针
        while(left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] <= target) left = mid;
            else right = mid - 1;
        }
        return {begin, right};
    }
};

总结：

1. 模板

// 找左端点
while(left < right)
{
    int mid = left + (right - left) / 2;
    if(...) left = mid + 1;
    else right = mid;
}

// 找右端点
left = 0, right = nums.size() - 1; // 重置指针
while(left < right)
{
    int mid = left + (right - left + 1) / 2;
    if(...) left = mid;
    else right = mid - 1;
}

助记：下面-1，上面就加一，判断情况就题论题

x的平方数

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

总结：

1. 提前处理边界情况
2. 本题实际上是找左端点，所以想左端点重要，写出判断条件

搜索插入位置

class Solution 
{
public:
    int searchInsert(vector<int>& nums, int target) 
    {
        // 实际上是找右端点
        int left = 0, right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        if(nums[left] < target) return left + 1;
        return left;
    }
};

总结：
本题实际是找左端点，需要注意的是要单独处理一下最后的特殊情况

山脉数组的峰顶索引

class Solution 
{
public:
    int peakIndexInMountainArray(vector<int>& arr) 
    {
        int left = 0, right = arr.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if(arr[mid] > arr[mid - 1]) left = mid;
            else right = mid - 1;
        }
        return left;
    }
};

总结：

1. 数组具有二段性，想到二分查找
2. 直接用模板，下面减一上面加一

寻找峰值

class Solution 
{
public:
    int findPeakElement(vector<int>& nums) 
    {
        int left = 0, right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] > nums[mid + 1]) right = mid; //如果中间值大于下一个值，就去左边一段查找，体会二段性
            else left = mid + 1; // 否则去右边一段查找
        }
        return left;
    }
};

总结：
3. 上减下加，模板很固定，没有出现则不用加
4. 存在二段性就能用二分查找，不用管数组是否有序

寻找旋转排序数组的最小值

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

总结：
5. 本题主要是找见二段行，一定要画图，理解两段，找见参照点

点名

class Solution 
{
public:
    int takeAttendance(vector<int>& records) 
    {
        int left = 0, right = records.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(records[mid] == mid) left = mid + 1;
            else right = mid;
        }
        return records[left] == left ? left + 1 : left; // 三目表达式的运用很方便
    }
};

总结：

1. 本题解法很多，如使用哈希表，遍历，位运算（异或），数组求和，二分法
2. 二分法关键是找二段性，本题的二段性在值和下标是否一一对应，注意要处理边界情况

完