Binary Search

Binary Search Python:

Finding target number in a sorted List

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif target < arr[mid]:
            right = mid - 1
        else:
            left = mid + 1
    return -1

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 5
print(binary_search(arr, target))  # Output: 4

 

Explanation:

left = 0
right = len(nums) - 1

# Loop until the bounds converge
while left <= right:
    # Find the midpoint of the current search bounds
    mid = left + (right - left) // 2

    # Check if the midpoint is the target
    if nums[mid] == target:
        return mid

    # If the target is less than the midpoint, search the left half
    elif target < nums[mid]:
        right = mid - 1

    # If the target is greater than the midpoint, search the right half
    else:
        left = mid + 1
# Return -1 if the target is not found
return -1