本文共 1928 字，大约阅读时间需要 6 分钟。

题目：统计一个数字在排序数组中出现的次数。例如输入排序数组为{1,2,3,3,,3,3,4,5}和数字3，由于3在这个数组中出现了4次，因此输出4

    既然输入的数组是排序的，那么我们很自然的想到利用二分查找算法。在题目给出的例子中，我们可以先用二分查找算法找到第一个3.由于3可能出现多次，因此我们找到的3的左右两遍可能都是3，于是我们在找到3的左右两边顺序扫描，分别找出第一个3和最后一个3.因为要查找的数字在长度为n的数组中可能很出现O(n)次，所以顺序扫描的时间复杂度为O(n)。因此这种算法的效率和直接从头到尾顺序扫描整个数组统计3出现的次数的方法是一样的。显然，面试官是不会满意这种算法，它会提示我们还有更快的算法。

    接下来我们思考如何更好的利用二分查找算法。假设我们统计数字k在排序数组中出现的次数。在前面的算法的时间主要消耗在如何确定重复出现的第一个k和最后一个k的位置上，有没有可以利用的二分查找算法直接找到第一个k和最后一个k。

    我们先分析如何利用二分查找在数组中找到第一个k，二分查找算法总是先拿数组的中间的数字和k做比较。如果中间的数字比k大，那么k只能出现在数组的前半段，下一轮我们旨在数组的前半段查找就可以了。如果中间的数字比k小，那么k只能出现在数组的后半段，下一轮我们只在数组的后半段查找就可以了。如果中间的数字和k相等呢？我们先判断这个数字是不是第一个k。如果位于中间数字的前面一个数字不是k，此时中间的数字刚好就是第一个k。如果中间的数字的前面一个数字也是k，也就是说第一个k肯定在数组的前半段，下一轮我们仍然需要在数组的前半段查找。

    同理我们利用上面的思路找到最后一个k。

    找到第一个k和最后一个k后就可以知道k出现的次数了。

private int getFirstK(int[] arr,int k,int left,int right){          if(left > right)              return -1;          int middleIndex = (left+right)/2;          int middleData = arr[middleIndex];          if(middleData == k){              if((middleIndex >0 && arr[middleIndex -1]!=k)|| middleIndex == 0)                  return middleIndex;              else                  right = middleIndex -1;          }          else if(middleData > k)              right = middleIndex -1;          else              left = middleIndex +1;          return getFirstK(arr,k,left,right);      }      private int getLastK(int[] arr,int k,int left,int right){          if(left > right)              return -1;          int middleIndex = (left + right)/2;          int middleData = arr[middleIndex];          if(middleData == k){              if((middleIndex 
   
    0){              int first = getFirstK(arr,k,0,arr.length-1);              int last = getLastK(arr,k,0,arr.length -1);              if(first >-1 && last >-1)                  number =last-first+1;          }          return number;      }
   

转载地址：http://lzgub.baihongyu.com/