没有人会为你踏雾而来，喜欢的风景要自己去看。

二分查找相信大家都应该不陌生，本次博主为大家带来的是一些有关二分查找变形的有关题目（来自剑指offer)，相信认真读完了后对初学者会有一定的帮助（我也是初学者，各位大佬不要喷我）

目录

​1 数字在有序数组中出现的次数​

 2 旋转数组的最小数字​

3 寻找峰值​

 4 二维数组的查找​

在此之前，我们先来做一个简单的练习温习一下最简单的二分查找：

最简单的二分查找​

这个题我相信大家都会，就不多讲了，具体代码：

int search(int* nums,int numlen,int target)
{
    if(numlen==0)
        return -1;
    if(numlen==1)
    {
        if(target==nums[0])
            return 0;
        else
            return -1;
    }
    int left=0;
    int right=numlen-1;
    int mid=0;
    while(left<=right)
    {
         mid=(left+right)/2;
        if(target>nums[mid])
            left=mid+1;
       else if(target<nums[mid])
            right=mid-1;
        else
            return mid;
    }
    return -1;
}

接下来就开始我们的正题了：

​1 数字在有序数组中出现的次数​

 题目描述：

给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数

数据范围：0≤n≤1000,0≤k≤1000 ，数组中每个元素的值满足 0≤val≤1000
要求：空间复杂度 O(1)，时间复杂度 O(logn)

示例1：

输入：[1,2,3,3,3,3,4,5],3

返回值：4

 示例2：

输入：[1,3,4,5],6

返回值：0

解题思路：

根据题目要求遍历数组肯定是行不通的，那么我们就要考虑用二分查找这种方法，假设我们给定一个数组[1,2,3,3,3,3,4,5]，要求3出现的次数，如果我们能找到比3恰好的位置，比3恰好的位置，两者相减就是要找到的数出现的次数。所以我们不妨将k-0.5的位置和k+0.5的位置找出来，上面k-0.5的位置为2，k+0.5的位置为6，相减恰好是k出现的次数4.

动图展示：

 具体代码：

int binaSerch(int*data,int dataLen,double k)
 {
     int left=0;
     int right=dataLen-1;

     while(left<=right)
     {
         int mid=left+((right-left)>>1);
         if(data[mid]>k)
         {
             right=mid-1;
         }
         else
         {
             left=mid+1;
         }
         
     }
     return left;
 }
int GetNumberOfK(int* data, int dataLen, int k ) {
    
    return binaSerch(data, dataLen, k+0.5) - binaSerch(data, dataLen, k-0.5);
}

注意事项：

1.  分装的二分查找函数中的k要用浮点型
2. 由于data[mid]不可能等于k,所以不需要判断他们相等的情况

 2 旋转数组的最小数字

 题目描述：

有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。

数据范围：1≤n≤10000，数组中任意元素的值: 0≤val≤100000

要求：空间复杂度：O(1)，时间复杂度：O(logn)

示例1：

输入：[3,4,5,1,2]

返回值：1

 示例2：

输入：[3,100,200,3]

返回值：3

解题思路：

由于数组是升序，我们可以知道当数组还没有旋转的时候最小值一定在最左边，旋转了后除了还未旋转外最左边的值不可能小于最右边的值，所以当最左边的数如果小于最右边的数时就可以直接返回最左边的数·（大家可以带一些值去试试）。

我们可以认为旋转后将原数组分成了两个有序的数组，现在关键是如何确定最小值在哪个区间，所以我们每次可以用中间值作比较来确定最小值的区间。

我们假定给出数组[1,2,3,4,5],旋转后的情况不外乎是：

[2,3,4,5,1]

[3,4,5,1,2]

[4,5,1,2,3]

[5,1,2,3,4]

通过上面我们发现：若是区间中点值大于区间右界值，则最小的数字一定在中点右边。

若是区间中点值小于区间右界值，则最小的数字一定在中点左边（包括中点）。

但是上面没有区间中点值等于区间右界值的情况，若是区间中点值等于区间右界值，则是不容易分辨最小数字在哪半个区间，比如[1,1,1,0,1]，应该逐个缩减右界。

 动图展示：

 具体代码：

int minNumberInRotateArray(int* rotateArray, int rotateArrayLen ) {
    // write code here
    int left=0;
    int right=rotateArrayLen-1;
    if(rotateArray[left]<rotateArray[right])
    {
        return rotateArray[left];
    }
    while(left<=right)
    {
        int mid=left+((right-left)>>1);
        if(rotateArray[mid] > rotateArray[right])
        {
            left=mid+1;
        }
        else if(rotateArray[mid] < rotateArray[right])
        {
            right=mid;
        }
        else
        {
            right--;
        }
    }
    return rotateArray[left];
}

 注意事项：

1.  可以先判断最左边的值与最右边值的大小，如果最左边的数小于最右边的数时就可以直接返回最左边的数
2. 区间中点值等于区间右界值的情况，应该逐个缩减右界

3 寻找峰值

题目描述;

给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。

1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于

2.假设 nums[-1] = nums[n] = −∞

3.对于所有有效的 i 都有 nums[i] != nums[i + 1]

4.你可以使用O(logN)的时间复杂度实现此问题吗？

数据范围：

1≤nums.length≤2×10^5

−2^31<=nums[i]<=2^31−1

如输入[2,4,1,2,7,8,4]时，会形成两个山峰，一个是索引为1，峰值为4的山峰，另一个是索引为5，峰值为8的山峰，如下图所示：

 示例1:

输入：[2,4,1,2,7,8,4]

返回值：1

说明：4和8都是峰值元素，返回4的索引1或者8的索引5都可以

示例2：

输入：[1,2,3,1]

返回值：2

说明：3 是峰值元素，返回其索引 2

解题思路：

题目要求时间复杂度为O(logN)，所以暴力求解肯定不行，因为题目将数组边界看成最小值，而我们只需要找到其中一个波峰，因此只要不断地往高处走，一定会有波峰。那我们可以每次找一个标杆元素，将数组分成两个区间，每次就较高的一边走，因此也可以用分治来解决，而标杆元素可以选择区间中点。

如果中间值大于它右边的值：我们不妨举个例子[x,x,x,5,4,x,x],其中x为任意值，我们可以带入一些值进去发现右边是不一定有坡峰的，如[x,x,x,5,4,5,4](有坡峰）[x,x,x,5,4,3,2](无坡峰），这也好解释由于右边是往下走的所以不能够确定峰值。但是左边一定是会有峰值的，同理我们可以来分析如果左边值是逐渐递减的如[9,8,6,5,4,x,x],我们可以知道9就是峰值，如果索引为2的值只要小于5那么5就是峰值，如果索引为2的值大于5那么索引为1的值如果小于索引为2的话索引为2就是峰值，否则索引为0的值如果大于索引为1的话索引为0就是峰值，否则索引为1的就是峰值。（这里关系比较复杂，大家可以自己去推推)。

同理如果中间值小于右边的元素，说明此时往右是向上，向上一定能有波峰。

 动图展示：

 具体代码：

int findPeakElement(int* nums, int numsLen ) {
    // write code here
    int left=0;
    int right=numsLen-1;
    while(left<right)
    {
        int mid=(left+right)/2;
        if(nums[mid]>nums[mid+1])
        {
            right=mid;
        }
        else
        {
            left=mid+1;
        }
    }
    return left;
}

注意事项：

1. while循环中没有加=，加了=后会出错
2. 往高处走一定有坡峰，当nums[mid]>nums[mid+1]时，中间值更大，所以向左缩短区间，nums[mid]<nums[mid+1]时，中间值右边更大，所以向右缩短区间。

 4 二维数组的查找

题目描述：

在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

[

[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]

]

给定 target = 7，返回 true。

给定 target = 3，返回 false。

数据范围：矩阵的长宽满足 0≤n,m≤5000， 矩阵中的值满足 0≤val≤10^9
进阶：空间复杂度 O(1)，时间复杂度 O(n+m)

 示例1：

输入：7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

返回值：true

说明:存在7，返回true

示例2：

输入：1,[[2]]

返回值：false

说明：不存在1，返回false

示例3：

输入：3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

返回值：false

说明：不存在3，返回false

 解题思路：

 这道题常规遍历肯定是行不通的，我们可以考虑用二分查找的思维来做题，二分查找就是不断的缩小区间直至我们找到我们想要找到的数据，我们通过题目描述不难发现这个二维数组其实就是一个杨氏矩阵（行从左到右依次递增，列从上到下依次递增），我们可以紧紧抓住这个条件，首先将数据定位到最右上边的元素（左下也行），如果要查找的元素比右上边的元素还大，那我们就可以排除这一行了，如果要查找的元素比右上边的元素还小，那么就可以排除这一列，然后迭代的走下去，注意控制循环结束的条件。

 动图展示：

 具体代码：

bool Find(int target, int** array, int arrayRowLen, int* arrayColLen ) {
    // write code here
    int row=0;
    int col=*arrayColLen-1;

    while(row < arrayRowLen  && col >= 0)
    {
        if(array[row][col] > target)
        {
            col--;
        }
        else if(array[row][col] < target)
        {
            row++;
        }
        else 
        {
            return true;
        }
    }
    return false;
}

注意事项：

 循环结束的条件要控制好。

结语

与二分查找相关的题目还有很多，但是终归这些题都是在如何利用已知条件来转换成我们所熟悉的二分方法，如果觉得博主的文章对你有帮助的话可不可以3连支持一下，后面博主还会持续更新剑指offer上的有关题目。