面试题53(2):0~n-1中缺失的数字

题目

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

解题思路

1. 二分查找
2. 若中间元素的值和下标相等，则下一轮只需查找右半边
3. 若中间元素的值和下标不相等，且它前面一个元素和它的下标相等，意味着中间的数字正好是第一个值和下标不相等的元素，它的下标就是数组中不存在的数字
4. 若中间元素的值和下标不相等且它前面一个元素和它的下标不相等，则下一轮查找需要在左半边进行

代码

class Solution{
  public:
    int getFirstk(int *sorted_array,int left,int right)
    {
        
        if(left <= right)
        {
            int index = (left + right) >> 1;
            int mid   = sorted_array[index];

            //if(index != mid)
            //{
            //    if(index == 0 || sorted_array[index-1] == index-1)
            //    {
            //        return mid;
            //    }
            //    right = index - 1;
            //}
            //else
            //{
            //    left = index + 1;
            //}
            if(index == 0 || (index != mid && sorted_array[index-1] == index-1))
            {
                return mid;
            }
            else if(index == 0 || (index !=mid && sorted_array[index-1] != index-1))
            {
                right  = index - 1;
            }
            else
            {
                left = index +1;
            }
            return getFirstk(sorted_array,left,right);
        }
        else
        {
            return -1;
        }
    }
    
    
};

完整代码见Github