在排序数组中查找缺失的数字

Question

这段代码有什么问题吗？无法使用二进制搜索在连续数组中搜索缺失的数字。

a = [1,2,3,4,5,7,8]

lent = len(a)
beg =0
end = lent-1

while beg < end:
    mid = (beg + end) / 2
    if (a[mid]-a[beg])==(mid - beg):
        beg = mid + 1
    else:
        end = mid -1
    if(beg == end):
        mid = (beg + end) / 2
        print "missing"
        print a[0]+ beg

Answer 1

更新#1：是的，还有一个错误。你是对的。这是更新版本

试试这个变体：

a = [1,2,3,4,5,7,8]

lent = len(a)
beg =0
end = lent-1

while beg < end:
    mid = (beg + end) / 2
    if (a[mid]-a[beg])==(mid - beg):
        beg = mid
    else:
        end = mid
    if abs(beg-end) <= 1:
        print "missing: %s" % (a[0] + max(beg, mid),)

结果：

missing: 6

此外，尝试使用函数，这样您就可以轻松地在不同的列表上测试和调试您的代码：

def find_missing(a):
    lent = len(a)
    beg =0
    end = lent-1

    while beg < end:
        mid = (beg + end) / 2
        if (a[mid]-a[beg])==(mid - beg):
            beg = mid
        else:
            end = mid
        if abs(beg-end) <= 1:
            return a[0] + max(beg, mid)

a = [1,2,3,4,5,7,8]
print find_missing(a)

a = [1,3,4,5,6]
print find_missing(a)

a = [1,2,3,4,5,7,8,9,10]
print find_missing(a)

结果：

6
2
6

Answer 2

int findMiss(int arr[], int low, int high)
{
    if(low>high)
        return -1;

     if(arr[low]-1 != low)
         return arr[low]-1;

     int mid = (low + high) / 2;
     if(arr[mid]-1 != mid)
         return findMiss(arr,low,mid);
     else
         return findMiss(arr,mid+1,high); 
}

Answer 3

//算法的实现使用java.

static int missingNumber(int [] nums) {
    int i=0;
    while(i < nums.length) {
        int correct = nums[i];
        if (nums[i] < nums.length && nums[i] != nums[correct]) {
            swap(nums, i, correct);
        } else {
            i++;
        }
        }

    for( int index=0; index<nums.length; index++){
        if(index != nums[index]) {
            return index;
        }
    }
    return nums.length;
}
static void swap(int[] nums, int first, int second) {
    int temp = nums[first];
    nums[first] = nums[second];
    nums[second] = temp;
}

在排序数组中查找缺失的数字

Find missing number in sorted array

binary-search