Introduction to binary search and detailed examples

Introduction to binary search

Binary search is also called half search. The basic idea of ​​binary search is to assume that the elements in the dictionary are stored in an array in an orderly manner from small to large. ,

First compare the given value key with the key of the element in the middle position of the dictionary. If they are equal, the retrieval is successful;

Otherwise, if the key is small, it will be in the first half of the dictionary. Continue the binary search in this part;

If the key is large, continue the binary search in the second half of the dictionary.

In this way, the retrieval interval is reduced by half after one comparison, and this continues until the retrieval is successful or fails.

Take any one of the two middle elements from an even number as the middle element

Binary retrieval is a more efficient retrieval method, which requires the dictionary to be sorted by key in the sequence table.

Code example:

#!/usr/bin/env python
import sys 
def BinarySearch(haystack, needle):
  low = 0 
  high = len(haystack) - 1 
  while(low <= high):
    mid = (low + high)/2
    midval = haystack[mid]
    if midval < needle:
      low = mid + 1 
    elif midval > needle:
      high = mid - 1 
    else:
      print mid 
      return mid 
  print -1
  return -1
if __name__ == "__main__":
  haystack = [int(i) for i in list(sys.argv[1])]
  needle = int(sys.argv[2])
  BinarySearch(haystack ,needle)

Run:

python@pythontab:~$ python BinarySearch.py 123456789 4
3

Remarks:

1.'__': Since python class members are all public and public It is accessed public and lacks private properties like traditional object-oriented languages.

So I just used __ to simulate private attributes. These __ attributes are often used internally and usually do not need to be overridden. No need to read either.

The purpose of adding two underscores is not to conflict with common public properties with the same name, and secondly to prevent users of the object (non-developers) from using it at will.

2.__name__ == "__main__" means that the program script is executed directly.

If it is not equal, it means that the script is imported by other programs. Then its __name__ attribute is Set to module name

The above is the detailed content of Introduction to binary search and detailed examples. For more information, please follow other related articles on the PHP Chinese website!