SoFunction
Updated on 2024-10-29

Pythonic version of binary lookup implementation process principle analysis

Prerequisites: ascending array, elements to be checked are in the array.

Dichotomous search: is a recursive function c. To be checked element a, the current array median b, if b = a then return the index of b, b & gt; a then in the subarray on the left side of b to call the function c, otherwise in the subarray on the right side of b to call the function c.

First thought, results after programming along the lines above:

def binary_search(index, a, value):
  if a[(len(a) - 1) // 2] == value:
    return index + (len(a) - 1) // 2
  elif a[(len(a) - 1) // 2] < value:
    return binary_search(index + (len(a) - 1) // 2 + 1, a[(len(a) - 1) // 2 + 1:], value)
  else:
    return binary_search(index, a[0:(len(a) - 1) // 2 + 1], value)

A second thought to simplify the logic of the median calculation:

def binary_search(index, a, value):
  if a[len(a) // 2] == value:
    return index + len(a) // 2
  elif a[len(a) // 2] < value:
    return binary_search(index + len(a) // 2, a[len(a) // 2:], value)
  else:
    return binary_search(index, a[0:len(a) // 2], value)

Third thought, remove return and replace it with lambda form:

binary_search = lambda index,a,value: index + len(a) // 2 if a[len(a) // 2] == value else binary_search(index + len(a) // 2, a[len(a) // 2:], value) if a[len(a) // 2] < value else binary_search(index, a[0:len(a) // 2], value)

Above is the binary search into the "one line of code" version of the process.

Run the test:

if __name__ == '__main__':
  a = [1, 2, 33, 43, 52, 66, 88, 99, 111, 120]
  print(f"Target index: {binary_search(0, a, value=33)}")

The results are as follows:

This is the whole content of this article, I hope it will help you to learn more.