力扣-二分查找

何为二分查找？

一个有序数组，然后两个指针，一个指向第一个left，一个指向最后一个right，然后计算mid。如果mid值大于指定值，那就right指向mid-1。如果小于则left指向mid+1.

69.x的平方根

69. x 的平方根 

题目

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

提示：

• 0 <= x <= - 1

题解

这个题目还是比较简单，有直接可以调用的库。

class Solution {
public:
    int mySqrt(int x) {
        int t=sqrt(x);
        return t;
    }
};

但是如果使用二分查找，应该如何解决问题呢。

首先求a的平方根，那么结果一定是在[1,a]之间。

这是一个有序数组。所以我们就可以使用二分查找。

class Solution {
public:
    int mySqrt(int x) {
        long long i=0;
        long long j=x/2+1;//对于一个非负数n，它的平方根不会大于（n/2+1）
        while(i<=j)
        {
            long long mid=(i+j)/2;
            long long res=mid*mid;
            if(res==x) return mid;
            else if(res<x) i=mid+1;
            else j=mid-1;
        }
        return j;
    }
};

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

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

题目

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10]
, target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10]
, target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

• 0 <= nums.length <=
•  <= nums[i] <=
• nums 是一个非递减数组
•  <= target <=

题解

在一个递增的数组中找target，找到数组中的第一个位置和第二个位置。

在这里可以使用二分查找的方法。

通过类似的方法，找到一个下限和一个上限。

如果mid的值大于等于target，那就right=mid。否则left=mid+1。

找最后一个位置（上限）的不同之处就是，如果mid大于target，那就right=mid。否则left=mid+1.

找第一个位置，就是尽量往左查找，所以mid的值等于target，right不变

找最后一个位置，就是尽量往右查找，所以mid的值等于target时，left+1.

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.size()==0)
            return vector<int>{-1,-1};
        int lower_=lower(nums,target);
        int high_=high(nums,target)-1;
        if(lower_==nums.size()||nums[lower_]!=target)
            return vector<int>{-1,-1};
        return vector<int>{lower_,high_};
    }
    int lower(vector<int> &nums,int target){
        int l=0,r=nums.size();
        while(l<r){
            int mid=(r+l)/2;
            if(nums[mid]>=target)
                r=mid;
            else
                l=mid+1;
        }
        return l;
    }
    int high(vector<int> &nums,int target){
        int l=0,r=nums.size();
        while(l<r){
            int mid=(r+l)/2;
            if(nums[mid]>target)
                r=mid;
            else
                l=mid+1;
        }
        return l;
    }
};

81.搜索旋转排序数组Ⅱ

81. 搜索旋转排序数组 II

题目

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

你必须尽可能减少整个操作步骤。

示例 1：

输入：nums = [2,5,6,0,0,1,2], target = 0输出：true

示例 2：

输入：nums = [2,5,6,0,0,1,2], target = 3输出：false

提示：

• 1 <= nums.length <= 5000
• - <= nums[i] <=
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• - <= target <=

题解（测试点275/282)

旋转排序数组，也就是排好序的数组首尾相连，然后从中间随机断开。从断开这里分开，两段都是有序的。

一开始思考的方向是，找到最大值，然后从最大值处断开。分两段进行查找。

但是这里有一个问题，就是可能出现多个最大值，如[2,2,2,0,1]

断开后就变成[2],[2,2,0,1]

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int n=max_element(nums.begin(),nums.end())-nums.begin();
        int l1=0,r1=n;
        int l2=n+1,r2=nums.size()-1;
        while(l1<=r1){
            int m1=(l1+r1)/2;
            
            if(nums[m1]<target)
                l1=m1+1;
            else if(nums[m1]>target)
                r1=m1-1;
            else
                return true;
        }
        while(l2<=r2){
            int m2=(l2+r2)/2;
            if(nums[m2]<target)
                l2=m2+1;
            else if(nums[m2]>target)
                r2=m2-1;
            else
                return true;
        }
        return false;
    }
};

正确题解

可以根据二分查找的方法，当mid与target值相等就返回true。

在查找过程中首先判断mid的值和target是不是相同，相同的话就要继续start++，这里就是解决之前所说的会有多个相同的数据，说明这里还不是我们的分割点。

如果不等于的话，可能会出现一部分是递增，另外一部分不是。这个时候我们就判断是否那一段是有序的，并且对那一段进行相应的判断。根据判断进行start和end的变化。

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int start=0,end=nums.size()-1;
        int mid;
        while(start<=end){
            mid=(start+end)/2;
            if(nums[mid]==target)
                return true;
            if(nums[start]==nums[mid])
                start++;
            else if(nums[mid]<=nums[end]){
                if(nums[mid]<target&&nums[end]>=target)
                    start=mid+1;
                else 
                    end=mid-1;
            }
            else{
                if(nums[mid]>target&&nums[start]<=target)
                    end=mid-1;
                else    
                    start=mid+1;
            }
        }
        return false;
    }
};