面试题53(剑指offer)--在排序数组中查找数字

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

示例：

Input:
    nums = 1, 2, 3, 3, 3, 3, 4, 6
    K = 3
Output:
    4

解法：

 public int getNumberOfK(int [] array , int k) {
        if (array.length==0||array==null){
            return 0;
        }
        int result=0;
        boolean flag=false;//标识是否找到数字
        for (int i : array) {
            if (i!=k&&flag){//找到数字且已遍历完找到的数字，跳出循环，减少遍历次数
                break;
            }
            if (i!=k){
                continue;
            }else {
                if (!flag){
                    flag=true;
                }
                result++;
                continue;
            }
        }
        return result;
    }

题目二： 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围为0～n-1之内。在范围0~n-1内的这n个数字中有且只有一个数字不在该数组中，请找出这个数字。

解法一：

 /**
     * arraySum记录数组的和，
     * numSum记录0到n-1的和，
     * 两个差即为缺失的数字，
     * 但是没有利用题上数组
     * 有序这个条件
     * @param sortedArray 数组
     * @param length 数组的长度
     * @return
     */
    public int lostNum(int[] sortedArray,int length){
        int arraySum=0;
        int numSum=0;
        for (int i : sortedArray) {
            arraySum+=i;
        }
        for (int j = 0; j <= length ; j++) {
            numSum+=j;
        }
        int result = numSum - arraySum;
        return result;
    }

解法二：

 /**
     * 如果从开始到当前位置不缺失数字，
     * 则当前的数组值与其下标值相等，
     * 说明缺失的值在当前值的后面，
     * 若数组值比当前下标值大，
     * 说明缺失的值在当前值之前，
     * 用二分法找到缺失的值
     * @param sortedArray
     * @param length
     * @return
     */
    public int lostNum(int[] sortedArray,int length){
        int start=0,end=length;
        while (start<end){
            int mid=(start+end)/2;
            if (sortedArray[mid]>mid) {
                end=mid;
            }else if (sortedArray[mid]==mid){
                start=mid+1;
            }
        }
        return start;
    }

题目三： 假设一个单调递增的数组里的每个元素都是整数并且是唯一的。请编程实现一个函数，找出数组中任意一个数值等于其下标的元素。例如，在数组{-3,-1,1,3,5}中，数字3和它的下标相等。

//与题目二第二种解法类似，同样是二分法，由于数组单调递增，所以，当数组值大于其下标值，说明当前数组值
//值之后的数组肯定大于其下标值，则若存在下标值与数组值相等的情况必在当前数组值之前，反之亦然。
public static int findNum(int[] sortedArray){
        int start=0;
        int end=sortedArray.length;
        while (start<end){
            int mid=(start+end)/2;
            if (sortedArray[mid]>mid) {
                end=mid;
            }else if (sortedArray[mid]<mid){
                start=mid+1;
            }else {
                return mid;
            }
        }
        return -1;//不存在相等返回-1
    }