数字在排序数组中出现的次数

题目描述

统计一个数字在排序数组中出现的次数。

解法一：

考虑到由于是排序数组，很自然联想到使用二分查找找到这个数字（有序或部分有序可以优先考虑二分查找），再从找到的这个数字两边遍历，便可以得到这个数字出现的次数。

public class Solution {
    public static int GetNumberOfK(int [] array , int k) {
       int low = 0, high = array.length, mid = 0;
       int count = 0;
       if(array.length == 0 || array == null)   //判断为空
           return 0;
       //通过二分查找定位数字
       //重要，切记要防止越界
       while(low <= high && low <= array.length - 1 && high >= 0) {    
           mid = (low + high) / 2;
           if(array[mid] == k)    //重要，找到该数字 
               break;
           else if(array[mid] > k) 
               high = mid - 1;
           else 
               low = mid + 1;
       }
       if(array[mid] != k)
           return 0;
       low = mid;
       high = mid + 1;
       while(low >= 0 || high < array.length) { if(low >= 0) {
               if(array[low] == k) 
                   count++;
           }
           if(high < array.length) {
               if(array[high] == k) 
                   count++;
           }
           low--;
           high++;
       }
       return count;
    }
}

虽然二分查找的时间复杂度为O（logn），但是由于从找到的数字向两边遍历时，遇到的全部数字均相同，则算法的时间复杂的退化为O（n），与直接顺序遍历整个数组没有差异，很明显这种解法并不好。
解法二：前一种算法之所以时间性能不好在于通过array[mid]获得的k值位置不定，我们需要遍历判断它前面有多少个k后面有多少个k，我们可以通过改进的二分查找直接找到第一个k和最后一个k，便很容易得到一共有多少个k了。

public class Solution {
    public static int GetNumberOfK(int [] array , int k) {
        if(array.length == 0 || array == null)
            return 0;
        int first = getFirstIndex(array, k);
        int last = getLastIndex(array, k);
        if(first == -1)
            return 0;
        else
            return last - first + 1;
        
    }
    public static int getFirstIndex(int [] array, int k) {
        int low = 0, high = array.length - 1, mid = 0;
        while(low <= high && low < array.length && high >= 0) {
            mid = (low + high) / 2;
            if(array[mid] == k) {
                if(mid >= 1) {
                    if(array[mid - 1] == k) 
                        high = mid - 1;
                    else
                        return mid;
                }
                else
                    return mid;
            }
            else if(array[mid] > k) 
                high = mid - 1;
            else 
                low = mid + 1;
        }
        if(array[mid] != k)
            return -1;
        else 
            return mid;
    }
    public static int getLastIndex(int [] array, int k) {
        int low = 0, high = array.length - 1, mid = 0;
        while(low <= high && low < array.length && high >= 0) {
            mid = (low + high) / 2;
            if(array[mid] == k) {
                if(mid <= array.length - 2) {
                    if(array[mid + 1] == k) 
                        low = mid + 1;
                    else
                        return mid;
                }
                else
                    return mid;
            }
            else if(array[mid] > k) 
                high = mid - 1;
            else 
                low = mid + 1;
        }
        if(array[mid] != k)
            return -1;
        else 
            return mid;
    }
}