在排序數組中找到缺失的數字

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