使用分而治之技术的二进制搜索

Question

算法正在运行，但只能查找值是否存在。我想找到索引以防它存在。我该怎么做？

def binarySearch(arr, num):
  if len(arr) == 1: #base case
    if arr[0] == num:
      return arr[0] #found
    else:
      return None #not found

  mid = int(len(arr)/2) 
  if arr[mid] > num:
    return binarySearch(arr[:mid], num)
  else:
    return binarySearch(arr[mid:], num)

print(binarySearch([1,2,3,4], 7)) #None
print(binarySearch([1,2,3,4], 3)) #3
print(binarySearch([1,2,3,4], 4)) #4
print(binarySearch([1], 2)) #None
print(binarySearch([1,2], 2)) #2

Answer 1

像这样传递索引：

def binarySearch(arr, num, idx=0):
  if len(arr) == 1: #base case
    if arr[0] == num:
      return idx
    else:
      return None #not found

  mid = len(arr) // 2
  if arr[mid] > num:
    return binarySearch(arr[:mid], num, idx)
  else:
    return binarySearch(arr[mid:], num, idx + mid)

print(binarySearch([1,2,3,4], 7)) #None
print(binarySearch([1,2,3,4], 3)) #2
print(binarySearch([1,2,3,4], 4)) #3
print(binarySearch([1], 2)) #None
print(binarySearch([1,2], 2)) #1

它现在 returns 号码的索引（如果已找到）或 None 如果它不在列表中。

如评论中所述：考虑传递起始值和结束值，而不是在每次递归时都复制列表。写起来和读起来更快更容易。

使用分而治之技术的二进制搜索

binary search using divide and conquer technique

python

binary-search

divide-and-conquer