Python Binary Search
Python3 ExamplesBinary search is a search algorithm for finding a specific element in a sorted array. The search process starts from the middle element of the array. If the middle element happens to be the element being searched for, the search process ends. If a specific element is greater or less than the middle element, the search continues in the half of the array that is greater or less than the middle element, and, like at the beginning, comparison starts from the middle element. If the array becomes empty at some step, it means the element is not found. This search algorithm halves the search range with every comparison.
Example: Recursion
# Return the index of x in arr, or -1 if it does not exist
def binarySearch (arr, l, r, x):
# Basic check
if r >= l:
mid = int(l + (r - l)/2)
# The element is exactly at the middle position
if arr[mid] == x:
return mid
# If the element is smaller than the element at the middle position, only need to compare the elements on the left
elif arr[mid] > x:
return binarySearch(arr, l, mid-1, x)
# If the element is greater than the element at the middle position, only need to compare the elements on the right
else:
return binarySearch(arr, mid+1, r, x)
else:
# Not found
return -1
# Test array
arr = [ 2, 3, 4, 10, 40 ]
x = 10
# Function call
result = binarySearch(arr, 0, len(arr)-1, x)
if result != -1:
print ("The index of the element in the array is %d" % result )
else:
print ("The element is not in the array")
Executing the above code produces the following output:
元素在数组中的索引为 3Other Extensions