<tip>对于有序数组一定要想到用二分查找。

一、普通的二分查找（数组中无重复元素）

1、二分查找的一般格式

int binarySerach(vector<int> &myvector,int target)
{
    int left=0,mid;
    int right=myvector.size();  ###(坑 1)或者myvector.size()-1
    while(left<right) //(坑2)或<=
    {
        mid=left+(right-left)/2;  #(坑3)
        if(myvector[mid]==target)
        {
            ###
        }
        else if(myvector[mid]<target)
            ###(坑4)
        else if(myvector[mid]>target)
            ###(坑5)
    }
    return left;
}

1.坑1：我们在取数组时可以取[0,n-1]也可以取[0,n），其中n为数组元素个数，此处要注意区间的开闭，两种不同的方式对于后面代码的书写时有影响的，其中直接影响的时坑2、4、5.
2.对于坑3，初学者会采用mid=(left+right)/2的写法，这种写法一般时候也可以AC，but留下了一个隐藏的bug，当我们left和right比较大的时候可能会出现数据溢出的情况。比如说同样是int类型的left=maxnum-2，right=max-4,正常情况下mid=max-3，（其中max为当前机器下所能表示的最大int数），此时如果我们采用mid=(left+right)/2表达式，会出现溢出现象。

2、二分查找闭区间书写格式

//程序在vs2015环境下运行
#include "stdafx.h"
#include<vector>
#include<iostream>
using namespace std;
int binarysearch(vector<int>&myvector, int target)
{
    int left = 0, right = myvector.size()-1;//[0,n-1]
    if (right == 0)
        return -1;
    int mid;
    while (left <= right)//跳出条件为left+1 = right,区间为[left+1,right]，保证了区间内无元素，即将整个数组检查了一遍
    {
        mid = left + (right - left) / 2;
        if (myvector[mid] == target)
            return mid;
        else if (myvector[mid] > target)
            //说明要查找的值在左侧区间[left,mid-1],要保证每个元素都不落下且不重复访问（若重复，在循环时可能卡在某个位置）
            right = mid - 1;
        else if (myvector[mid] < target)
            //说明要查找的值在左侧区间[mid+1,right]
            left = mid + 1;
    }
    return -1;
}
int main()
{
    vector <int>nums = {1,2,5,8,9,11,45,45,89};
    cout<<binarysearch(nums, 45);
    int nn;
    cin >> nn;
    return 0;
}

测试结果

image.png

结果分析：此时可以将45在数组中查找出来，但是nums数组中有重复的45，只查找出来了第一个45的位置，当nums数组中元素改变时也可能查找出第二个45，即只能保证找到，但是位置不好确定，所以对于有重复数据的有序数组，二分查找需要进行改进（见第二部分），才可查到最左/右的边界元素。

3、二分查找开区间书写格式

int binarysearch2(vector<int>&myvector, int target)
{
    int left = 0, right = myvector.size() ;//[0,n)
    if (right == 0)
        return -1;
    int mid;
    while (left < right)//跳出条件为left = right,区间为[left,right)，保证了区间内无元素，即将整个数组检查了一遍
    {
        mid = left + (right - left) / 2;
        if (myvector[mid] == target)
            return mid;
        else if (myvector[mid] > target)
            //说明要查找的值在左侧区间[left,mid)要保证每个元素都不落下且不重复访问（若重复，在循环时可能卡在某个位置）
            right = mid;
        else if (myvector[mid] < target)
            //说明要查找的值在左侧区间[mid+1,right)
            left = mid + 1;
    }
    return -1;
}

二、改进的二分查找（数组中有重复元素）

此知识点主要涉及两种问题，1、寻找左边界的index，2、寻找右边界的index

3、寻找左边界

对于容器vector <int>nums = {1,2,5,8,9,45,45,45,89};中，想要查找到第一个45，返回index=5。
思路：我们先正常去查45，假设查到了第二个45，这时我们让right指针指向这个位置，right=mid然后查[left,right）区间中的45，即区间数组变成了{1,2,5,8,9,45}，在此区间如果有45，则查到后继续用right指向，如果没有45，说明上一次查找过程找到的45时最左侧的，返回return right;即可。

int binarysearch3(vector<int>&myvector, int target)
{
    int left = 0, right = myvector.size() ;//[0,n)
    if (right == 0)
        return -1;
    int mid;
    while (left < right)//跳出条件为left = right,区间为[left,right)，保证了区间内无元素，即将整个数组检查了一遍
    {
        mid = left + (right - left) / 2;
        if (myvector[mid] == target)
            right = mid;//将查找到的值作为右端（重点）
        else if (myvector[mid] > target)
            //说明要查找的值在左侧区间[left,mid)要保证每个元素都不落下且不重复访问（若重复，在循环时可能卡在某个位置）
            right = mid;
        else if (myvector[mid] < target)
            //说明要查找的值在左侧区间[mid+1,right)
            left = mid + 1;
    }
    return right;
}
int main()
{
    vector <int>nums = {1,2,5,8,9,11,45,45,45,45,88,89};
    cout<<binarysearch3(nums, 45);
    int nn;
    cin >> nn;
    return 0;
}
//输出结果为6

4、寻找右边界

思路：同上，将查到的值作为区间的左侧nums = {1,2,5,8,9,45,45,45,89}，若查到第二个45，left=mid+1则此后的区间为{45,89}，继续查找45，如果有则将left后移，若没有说明刚刚的mid时最后一个45值，注意此时mid=left-1,所以返回值应为return left-1;。

int binarysearch4(vector<int>&myvector, int target)
{
    int left = 0, right = myvector.size() ;//[0,n)
    if (right == 0)
        return -1;
    int mid;
    while (left < right)//跳出条件为left = right,区间为[left,right)，保证了区间内无元素，即将整个数组检查了一遍
    {
        mid = left + (right - left) / 2;
        if (myvector[mid] == target)
            left = mid+1;//将查找到的值作为右端（重点）
        else if (myvector[mid] > target)
            //说明要查找的值在左侧区间[left,mid)要保证每个元素都不落下且不重复访问（若重复，在循环时可能卡在某个位置）
            right = mid;
        else if (myvector[mid] < target)
            //说明要查找的值在左侧区间[mid+1,right)
            left = mid + 1;
    }
    return left-1;
}
int main()
{
    vector <int>nums = {1,2,5,8,9,11,45,45,45,45,88,89};
    cout<<binarysearch4(nums, 45);
    int nn;
    cin >> nn;
    return 0;
}
//输出为9

三、二分查找常见题型

3.1 剑指 Offer 11. 旋转数组的最小数字

image.png

解题思路：二分查找的变形，此题是两个内部有序递增的数组，且数组2的最大值<=数组1的最小值。
我们同样可以设置三个指针int left=0, right=n-1 , mid=left + (right - left) / 2;然后进行分情况讨论。

if(nums[mid]<nums[right])说明mid出现在了右侧的数组中，此时拐点（尖点）在mid的左侧(或mid就是尖点，如3，1，3)，答案肯定在闭区间[ left,mid ]中，即right=mid。

image.png
if(nums[mid]>nums[right])说明有且仅有一种可能，即mid出现在了左侧的数组中，right在右侧数组中，此时拐点（尖点）在mid的右侧，答案肯定在闭区间[ mid+1,right ]中，即left=mid+1。

image.png
if(nums[mid]==nums[right])例如数组{4，4，4，4，6，1，2，4}left=0,right=7,mid=7/2=3即加粗元素4与尾元素相等了。此时我们已经明确的知道最后一个元素4不是我们的答案，所以将right--来解决尴尬的处境，也曾考虑过将左侧后移，但是情况比较复杂，不能处理。

image.png

class Solution {
public:
    int minArray(vector<int>& numbers) {
        //二分查找+暴力 
        int left=0;
        int right =numbers.size()-1;
        int mid;
        if(right<1)
        return numbers.front();        
        while(left<=right)
        {
            mid=(left+right)/2;
            if(numbers[mid]<numbers[right])
            {
                right=mid;
            }
            else if(numbers[mid]>numbers[right])
            {
                left=++mid;
            }
            else
            {
                right--;
            }
        }
        return numbers[left];
    }
};

代码性能分析：
1、本题第一次我采用遍历的策略，找到第一个突变点，然后打印返回，此时复杂度为O(n)。以后针对于有序数组要第一时间想到二分查找，
2、本题的解法为什么叫二分查找+暴力呢？因为情况好的情况下时间复杂度是O(logn),当数组全为重复元素时候，只能执行right--，退回到了遍历的阶段，时间复杂度也降到了O(n)。

3.2剑指 Offer 53 - I. 在排序数组中查找数字 I

image.png

解题思路：看到数组有序，首选二分查找，此题返回重复数字的个数，针对于前面的基础知识，我们知道用改进的二分算法可以定位到右边界right和左边界left，出现的次数res=right-left+1

class Solution {
public:
    int search(vector<int>& nums, int target) {
        //两次二分查找先找到左边届le,再找到右边界ri，res=ri-le+1
        int left=0,mid,right=nums.size();
        if(left==right)
            return 0;
        int res=0;
        //左边界查找（right值一直等于target，逐渐向左逼近）
        while(left<right)
        {
            mid=left+(right-left)/2;
            if(nums[mid]==target)
                right=mid;
            else if(nums[mid]>target)
                right=mid;
            else if(nums[mid]<target)
                left=mid+1;
        }
        int le=left;
        //查找右边界，left值一直等于target，逐渐向右逼近，直到最后一个target的下一位置
        left=0,right=nums.size();
        while(left<right)
        {
            mid=left+(right-left)/2;
            if(nums[mid]==target)
                left=mid+1;
            else if(nums[mid]>target)
                right=mid;
            else if(nums[mid]<target)
                left=mid+1;
        }
        int ri=left-1;
        res=ri-le+1;
        return res;
    }
};

代码性能分析：
1、常规解法：从前向后遍历，遇到target开始计数，时间复杂度为O(n)。
2、二分解法：使用两次二分查找，时间复杂度为O(logn)。

二分查找详解+练习剑指 Offer11 剑指 Offer53

二分查找详解+练习剑指 Offer11 剑指 Offer53

一、普通的二分查找（数组中无重复元素）

1、二分查找的一般格式

2、二分查找闭区间书写格式

3、二分查找开区间书写格式

二、改进的二分查找（数组中有重复元素）

3、寻找左边界

4、寻找右边界

三、二分查找常见题型

3.1 剑指 Offer 11. 旋转数组的最小数字

image.png

3.2剑指 Offer 53 - I. 在排序数组中查找数字 I

image.png

二分查找详解+练习剑指 Offer11 剑指 Offer53

一、普通的二分查找（数组中无重复元素）

1、二分查找的一般格式

2、二分查找闭区间书写格式

3、二分查找开区间书写格式

二、改进的二分查找（数组中 有 重复元素）

3、寻找左边界

4、寻找右边界

三、二分查找常见题型

3.1 剑指 Offer 11. 旋转数组的最小数字 image.png

3.2剑指 Offer 53 - I. 在排序数组中查找数字 I image.png

二、改进的二分查找（数组中有重复元素）

3.1 剑指 Offer 11. 旋转数组的最小数字

image.png

3.2剑指 Offer 53 - I. 在排序数组中查找数字 I

image.png