下列二分枚举算法中,{ }处应该填入的程序是({}不算做程序的一部分)( )。
def binary_search(arr, x): low = 0 high = len(arr) - 1 while low <= high: { } return -1
mid = (low + high) // 2 if arr[mid] == x: return mid elif arr[mid+1] > x: high = mid - 1 else: low = mid + 1
mid = (low + high) // 2 if arr[mid] != x: return mid elif arr[mid+1] > x: high = mid - 1 else: low = mid + 1
mid = (low + high) // 2 if arr[mid] == x: return mid elif arr[mid] > x: high = mid - 1 else: low = mid + 1
mid = (low + high) // 2 if arr[mid] != x: return mid elif arr[mid] > x: high = mid - 1 else: low = mid + 1
对于有序序列arr,从中找x的位置,判断arr[mid+1]是不正确的,所以排序AB,然后如果arr[mid]==x,应该是找到了x的位置,直接return mid即可。