二分查找算法—C++

一，二分查找

 1，题目描述

在一个给定的有序数组中，查找目标值target，返回它的下标。如果不存在，返回-1

2，思路

解法一：暴力枚举，遍历整个数组，直到找到目标值，返回下标。

解法二：利用数组的有序性，使用二分查找算法。使用两个指针left和right来维护要查找的区间，每次使用该区间的中间值与target目标值比较。图示：

3，代码实现 

class Solution {
public:
    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)
               right=mid-1;
            else if(nums[mid]<target)
              left=mid+1;
            else
              return mid;//找到了
        }
        return -1;
    }
};

4，总结朴素二分模板

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

1，题目描述

在一个整数数组中找到target目标值第一次出现的位置，和最后出现的位置。

2，思路

解法一：题目中数组是有序的，所以我们可以利用二分查找的二段性思想来解决，所谓二段性，就是通过某种规律可以将数组分成两部分，再通过判断我们可以舍去一部分。从而加快查找。

图示：以查找target第一次出现的位置为例

同理，查找最后一次出现的位置

细节问题：

3，代码实现 

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> v;
        if (nums.size() == 0)
            return {-1, -1};
        // 查找第一次出现的位置
        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)
            v.push_back(left);
        else
            v.push_back(-1);

        // 查找最后一次出现的位置
        //left可以选择不从0开始，从当前位置，也就是第一次出现的位置开始
        right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] > target)
                right = mid - 1;
            else
                left = mid;
        }
        if (nums[left] == target)
            v.push_back(left);
        else
            v.push_back(-1);

        return v;
    }
};

4，总结二分模板

关于求中点位置的操作什么时候需要加1，什么时候不需要。只需看下面的left和right ，如果出现-1，mid就需要加1。否则，不需要加1.

三，x的平方根

1，题目描述

 给你一个数x,求它的平方根。

2，思路

解法一：枚举，从1开始计算平方，直到计算到等于x的值，并返回

解法二：二段性，二分查找

3，代码实现 

四，山脉数组的峰顶索引

1，题目描述

给你一个山脉数组，数组的值是先上升后下降的，求峰顶值的下标

2，思路

 解法一：暴力解法，遍历数组，找到第一次出现，前一个元素大于后一个元素的位置，时间复杂度为O(N)

解法二：二分查找，图示

 3，代码实现

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;
    }
};