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

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

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

最简单的二分查找

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

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,所以不需要判断他们相等的情况
3. 
   

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. 区间中点值等于区间右界值的情况，应该逐个缩减右界