Implementation of Binary Search Method in python

If you want to find the desired data in the ordered data, the 2-point search method is a good method, which can greatly shorten the search time and is a common search method. 2-point search is very good to write, but it is difficult to write right, below, this site will simply introduce 1 under 2-point search, and demonstrate the code used by the device.

1, 2 points search

In an ordered and non-repeating list, find the elements of the list.

2. Characteristics

(1) Must be directed at ordered lists

(2) The list must be free of duplicates

(3) Lookup by subscript index

3. How to use it

Non-recursive implementation:

def binary_search(alist, item):
  """2 Separate search   Non-recursive mode """
  n = len(alist)
  start = 0
  end = n - 1
  while start <= end:
    mid = (start + end) // 2
    if alist[mid] == item:
      return True
    elif item < alist[mid]:
      end = mid - 1
    else:
      start = mid + 1
  return False

if __name__ == '__main__':
  li = [17, 20, 26, 31, 44, 54, 55, 77, 93]
  # print(binary_search(li, 55))
  # print(binary_search(li, 100))

Recursive implementation:

def binary_search_2(alist, item):
  """2 Separate search   Recursive mode """
  n = len(alist)
  if 0 == n:
    return False
  mid = n // 2
  if alist[mid] == item:
    return True
  elif item < alist[mid]:
    return binary_search_2(alist[:mid], item)
  else:
    return binary_search_2(alist[mid + 1:], item)
if __name__ == '__main__':
  li = [17, 20, 26, 31, 44, 54, 55, 77, 93]
  # print(binary_search(li, 55))
  # print(binary_search(li, 100))

Extension of basic knowledge points:

Introduction

Two-point search is also called half-fold search (Binary Search), which is a highly efficient search method. However, halved lookup requires that the linear table must be stored in sequential structure, and the elements in the table are ordered by keywords.

Premise

The sequence to be found must be ordered

Time complexity

O(log2n)

Principle

1) Determine the intermediate position K during this period

2) Compare the searched values t with array [k]. If they are equal, the search is successful and returns to this position; Otherwise, a new search area is determined, and the search is continued for 2 minutes.

3) Region determination process:

If array [k] > t, because the array is ordered, so array [k, k+1,..., high] > t; Therefore, the new interval is array [low,..., K-1];

Conversely, if array [k] < t corresponds to a lookup interval of array [k+1,..., high]