Python Program for Binary Search with Example and Explanation

A Python program for binary search uses a loop or recursion to repeatedly divide a sorted list and check the middle element with mid = (low + high) // 2, adjusting low or high until the target is found or the search space is empty.

Examples

Inputarr = [1, 3, 5, 7, 9], target = 7

OutputIndex of 7 is 3

Inputarr = [2, 4, 6, 8, 10], target = 5

Output-1 (not found)

Inputarr = [10], target = 10

OutputIndex of 10 is 0

How to Think About It

To find a number in a sorted list, start by looking at the middle item. If it matches the number, you are done. If the number is smaller, look only in the left half. If it is bigger, look only in the right half. Repeat this until you find the number or there is no more list left.

Algorithm

1

Set low to 0 and high to the last index of the list.

2

While low is less than or equal to high:

3

Calculate mid as the middle index between low and high.

4

If the middle element equals the target, return mid.

5

If the middle element is less than the target, set low to mid + 1.

6

Else, set high to mid - 1.

7

If the loop ends without finding the target, return -1.

Code

python

def binary_search(arr, target):
    low, high = 0, 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 usage
arr = [1, 3, 5, 7, 9]
target = 7
result = binary_search(arr, target)
print(f"Index of {target} is {result}" if result != -1 else "-1 (not found)")

Output

Index of 7 is 3

Dry Run

Let's trace the search for target 7 in the list [1, 3, 5, 7, 9].

1

Initial pointers

low = 0, high = 4

2

Calculate mid

mid = (0 + 4) // 2 = 2, arr[mid] = 5

3

Compare mid value with target

5 < 7, so set low = mid + 1 = 3

4

Calculate new mid

mid = (3 + 4) // 2 = 3, arr[mid] = 7

5

Found target

arr[mid] == target, return index 3

low	high	mid	arr[mid]	action
0	4	2	5	5 < 7, move low to 3
3	4	3	7	Found target, return 3

Why This Works

Step 1: Divide the search space

The code calculates the middle index with mid = (low + high) // 2 to split the list into halves.

Step 2: Compare middle element

It compares the middle element with the target to decide which half to search next.

Step 3: Adjust search range

If the middle element is less than the target, it moves the low pointer up; otherwise, it moves the high pointer down.

Step 4: Repeat until found or empty

This process repeats until the target is found or the search range is empty, returning -1 if not found.

Alternative Approaches

Recursive binary search

python

def binary_search_recursive(arr, target, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, high)
    else:
        return binary_search_recursive(arr, target, low, mid - 1)

arr = [1, 3, 5, 7, 9]
target = 7
result = binary_search_recursive(arr, target)
print(f"Index of {target} is {result}" if result != -1 else "-1 (not found)")

Uses recursion instead of a loop; easier to read but uses more memory due to call stack.

Using Python's bisect module

python

import bisect

def binary_search_bisect(arr, target):
    index = bisect.bisect_left(arr, target)
    if index != len(arr) and arr[index] == target:
        return index
    return -1

arr = [1, 3, 5, 7, 9]
target = 7
result = binary_search_bisect(arr, target)
print(f"Index of {target} is {result}" if result != -1 else "-1 (not found)")

Uses built-in module for binary search; very concise and efficient but less educational.

Complexity: O(log n) time, O(1) space

Time Complexity

Binary search cuts the search space in half each step, so it runs in logarithmic time, O(log n).

Space Complexity

The iterative version uses constant extra space, O(1), as it only stores a few variables.

Which Approach is Fastest?

Iterative binary search is fastest in practice due to no recursion overhead; using bisect is concise and optimized but less instructive.

Approach	Time	Space	Best For
Iterative binary search	O(log n)	O(1)	General use, memory efficient
Recursive binary search	O(log n)	O(log n)	Clear code, but uses call stack
bisect module	O(log n)	O(1)	Quick, built-in, less code