剑指offer：数字在排序数组中出现的次数（二分查找 leetcode 34）

题目：

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

答案：

解法一：

直接遍历，代码如下：

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
       if(array==null||array.length==0){
           return 0;
       }
        int count = 0;
        for(int i=0;i<array.length;i++){
            if(array[i]>k){
                return count;
            }else if(array[i]==k){
                count++;
            }
        }
        return count;
    }
}

解法二：

其实一看到是排序的数组，就想到了二分查找

参考链接：https://blog.csdn.net/wyplj2015/article/details/104795819

代码如下：

public class Solution {
    int lIndex = -1,rIndex = -1;
    public int GetNumberOfK(int [] array , int k) {
       if(array==null||array.length==0){
           return 0;
       }
        leftIndex(array,k);
        rightIndex(array,k);
        return lIndex>-1?rIndex-lIndex+1:0;
    }
    public void leftIndex(int[] array,int k){
        int left = 0;
        int right = array.length-1;;
        while(left<=right){
            int mid = (left+right)/2;
            if(array[mid]>k){
                right = mid-1;
            }else if(array[mid]<k){
                left = mid+1;
            }else{
                lIndex = mid;
                right = mid-1;
            }
        }
    }
    public void rightIndex(int[] array,int k){
        int left = 0;
        int right = array.length-1;
        while(left<=right){
            int mid = (right+left)/2;
            if(array[mid]>k){
                right = mid-1;
            }else if(array[mid]<k){
                left = mid+1;
            }else{
                rIndex = mid;
                left = mid+1;
            }
        }
    }
}

解法三：

直接使用Arrays.binarySearch方法，获得一个k的位置（无法保证这个位置是是不是开始位置），然后从开始位置想左右遍历，代码如下：

import java.util.*;
public class Solution {
    public int GetNumberOfK(int [] array , int k) {
       if(array==null||array.length==0){
           return 0;
       }
        int index = Arrays.binarySearch(array,k);
        if(index<0){
            return 0;
        }
        int count = 1;
        for(int i=index+1;i<array.length;i++){
            if(array[i]>k){
                break;
            }
            count++;
        }
        for(int i=index-1;i>=0;i--){
            if(array[i]<k){
                break;
            }
            count++;
        }
        
        return count;
    }

}