程序员面试之在有序数组中找到指定数的个数

　　题目：在一个有序数组中找到一个指定数k的个数
　　例如[1,1,2,2,2,3,4,4,4,4,5,6,7,8]，给出2，返回3，因为2出现了3次
　　出现频率：四星
　　难度： 三星
　　思路：由于是有序数组，自然会想到二分法查找，但实际上，这道题的难度大于二分查找，经常出现在笔试的最后一道，在已经掌握二分法查找的方法下（关于二分法查找可以查阅我的另一篇博文），比较容易想到的思路是先利用2分法找到指定数的索引位置n,然后从n+1开始顺序遍历下去计数等于k的个数，同时从n-1的位置向0索引位置遍历计数等于k的个数，两者相加就得到了答案。但是这个解题思路只能得50分，因为如果出现大量的重复k的这个数的数组，查找效率将急剧下降，例如：
　　[1,1,2,2,2,2.........................2,2,2,3,4,5,6,6,7,7,7,8]
　　在这个数组中查找2，的时间复杂度将大大超过log(N)
　　正确的思路是，循环二分，在二分查找到指定数的情况下，在2头继续二分，直到高低位索引相遇，在循环2分过程中。不断替换找到的这个数的最大索引和最小索引, 记为minindex和maxindex,最后的结果就是maxindex-minindex+1.这个算法在指定结果数出现大量重复时的查找时间复杂度依然是log(N)
　　当然，在紧张的面试中，留给这道题的时间只有15分钟左右，要想在15分钟时间把这道题写对没有那么容易，在这里交给大家一些技巧
　　1.先假设2分法已经写好，最后来补全,避免代码量太大笔试时间不够
　　2.利用递归，在实际做项目时，递归并不好，一来运行效率不高。二来容易死循环或者栈溢出，但是在笔试中确实一个利器，运用好递归事半功倍
　　下面是GO语言代码:package main  package main  import ＂fmt＂  //2分查找 func Find( n int, a [] int,  low int, high int) int {     mid :=0     for     {         if low > high{              return -1         }         mid=(low+high)/2;        //find        if(n==a[mid]){             return mid;        }else if(n>a[mid]){           low=mid+1;       }else{        high=mid-1;       }     }     return -1; }  var count = 0 var minindex = -1 var maxindex = -1  func Count( a [] int, k int, start int, end int ){     if start > end{         return     }     index := Find( k, a, start,end )         //调用2分查找     if index  == -1{         return 	 }         if index > maxindex{                 //循环替换找到的最大索引         maxindex = index     }     if index < minindex{                  //循环替换找到的最小索引         minindex = index     }     if index + 1 < len(a) && a[index + 1] == k{         Count( a,k, index+1, end )     }          if index - 1 >= 0 && a[index-1] == k{         Count( a, k, start, index-1 )     }    }  func main() {         var a = []int{1, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 6, 8, 8}    k := 4    minindex = len(a) -1    Count(a,k,0,len(a)-1)    count = maxindex - minindex + 1   if count < 0{                //如果没有找到minindex会大于maxindex     count = 0              }    fmt.Println(＂结果是＂,count) }
　　输出结果是5，时间复杂度是log(N)