Python Program to Implement Binary Search

Document 对象参考手册Python3 Examples

Binary search is an efficient search algorithm for sorted arrays. It gradually narrows the search range by dividing the array in half until the target element is found or it is determined that the target element does not exist.

Example

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

# Example array
arr = [1, 3, 5, 7, 9, 11, 13, 15]
target = 7

# Call the binary search function
result = binary_search(arr, target)

if result != -1:
    print(f"Element {target} is at index {result} in the array")
else:
    print(f"Element {target} is not in the array")

Code analysis:

  1. binary_searchThe function takes two parameters:arris the sorted array,targetis the target element to search for.
  2. lowandhighrepresent the lowest and highest indices of the current search range, respectively.
  3. whileThe loop continues whilelowis less than or equal tohigh, indicating that the search range is still valid.
  4. midCalculate the middle index of the current search range.
  5. Ifarr[mid]equalstarget, returnmid, indicating that the target element has been found.
  6. Ifarr[mid]is less thantarget, adjustlowismid + 1, indicating that the target element is in the right half.
  7. Ifarr[mid]is greater thantarget, adjusthighismid - 1, indicating that the target element is in the left half.
  8. If the loop ends without finding the target element, return-1, indicating that the target element is not in the array.

Output result:

元素 7 在数组中的索引是 3

Document 对象参考手册Python3 Examples

Other extensions