Pyfied
Log in
ProgramAlgorithms

Python Binary Search Program (Iterative and Recursive)

By (LinkedIn) · Every code example is run and checked on Python 3.13 (how we test) · Last updated

Short answer
Binary search finds a value in a sorted list by repeatedly comparing the target with the middle item and discarding the half that cannot contain it. It runs in O(log n) time and returns the index or -1.

If you look up a word in a printed dictionary, you do not read it from page one. You open it near the middle, decide whether your word comes before or after, and repeat on the correct half. Binary search does exactly that with a list.

The one hard rule: the list must already be sorted. On unsorted data the answer is meaningless. If your data is unsorted and you search it only once, linear search is simpler and just as good; if you will search many times, sort once and then use binary search.

InputA sorted list and a target value
OutputIndex of the target, or -1 if it is missing
ApproachKeep a low and high boundary, test the middle, halve the range each time
Time complexityO(log n); O(1) extra space for the iterative version

Approach: binary search step by step

  1. Set low = 0 and high = len(items) - 1.
  2. While low <= high, compute mid = (low + high) // 2.
  3. If items[mid] equals the target, return mid.
  4. If items[mid] is smaller than the target, the target can only be to the right, so set low = mid + 1.
  5. Otherwise it can only be to the left, so set high = mid - 1.
  6. When the loop ends with low > high, the range is empty: return -1.

Each pass throws away half of the remaining items. A list of 1,000,000 items needs at most about 20 comparisons.

How the binary search code works

The loop condition low <= high means "there is still at least one item to look at". The floor division // (see Python numbers) keeps mid an integer. The + 1 and - 1 are essential: mid has already been checked, so moving the boundary past it guarantees the range shrinks every iteration and the while loop always ends.

Watch the boundaries move for the target 23:

Python 
items = [2, 5, 8, 12, 16, 23, 38, 56]
low, high = 0, len(items) - 1
while low <= high:
    mid = (low + high) // 2
    print("low", low, "high", high, "mid", mid, "value", items[mid])
    if items[mid] == 23:
        break
    elif items[mid] < 23:
        low = mid + 1
    else:
        high = mid - 1





      
      
    

    
    
    

      
Binary search with bisect and recursion

      
The standard library module bisect implements the hard part. bisect_left(items, target) returns the position where the target is, or would be inserted to keep the list sorted, so you only need to confirm the item is really there. A recursive version is also possible (it follows the same idea as recursion), but the loop is usually clearer and avoids deep call stacks.

      
      
    

    
    
    

      
Binary search vs linear search

      
      
      
      

        
        
AspectLinear searchBinary search

        
List must be sorted?NoYes
Worst-case comparisonsnabout log2(n)
Time complexityO(n)O(log n)
Best forSmall or unsorted listsLarge sorted lists searched often
Code complexityVery simpleEasy to get boundaries wrong

      

      
    

    
    

    
    

      
Examples you can run

      
Press Run, then edit the code and run it again.

      
      

        
Iterative binary search on sorted scores

        
The program finds an existing value and reports -1 for a missing one.

        

  

    Iterative binary search on sorted scores
    

      
      
      
      
    

  

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

scores = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(scores, 23))
print(binary_search(scores, 2))
print(binary_search(scores, 91))
print(binary_search(scores, 40))

  
  
  
  

    
      
      
    
    
  

  
Expected output5
0
9
-1




      

      
      

        
Alternative: binary search with bisect

        
bisect_left does the halving in fast C code. Check bounds before comparing, because the insertion point can equal len(items).

        

  

    Alternative: binary search with bisect
    

      
      
      
      
    

  

  
from bisect import bisect_left

def search(items, target):
    pos = bisect_left(items, target)
    if pos < len(items) and items[pos] == target:
        return pos
    return -1

prices = [99, 149, 249, 399, 799]
print(search(prices, 249))
print(search(prices, 300))
print(search(prices, 1000))

  
  
  
  

    
      
      
    
    
  

  
Expected output2
-1
-1




      

      
      

        
Edge cases: empty list, one item and duplicates

        
With duplicates binary search may return any matching index, not necessarily the first one.

        

  

    Edge cases: empty list, one item and duplicates
    

      
      
      
      
    

  

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

print(binary_search([], 7))
print(binary_search([7], 7))
print(binary_search([7], 3))
print(binary_search([1, 2, 2, 2, 3], 2))

  
  
  
  

    
      
      
    
    
  

  
Expected output-1
0
-1
2




      

      
      

        
Interactive lookup of a product code

        
The user types a number and the program searches a sorted list of product codes. int() converts the typed text first (see converting strings to int).

        

  

    Interactive lookup of a product code
    

      
      
      
      
    

  

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

codes = [101, 205, 310, 422, 518, 640, 777]
code = int(input("Product code: "))
position = binary_search(codes, code)
if position == -1:
    print("Code not found")
else:
    print("Found at index", position)

  

  
  
  

    
      
      
    
    
  

  
Expected outputProduct code: 518
Found at index 4




      

      
    

    

    
    

      
Common mistakes

      
      

        
Searching an unsorted list

        

          
✗ Wrong
def binary_search(items, target):
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

print(binary_search([9, 1, 7, 3, 5], 1))
-1 (wrong: 1 is in the list, but the halving logic assumed sorted order)

          
✓ Right
def binary_search(items, target):
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

print(binary_search(sorted([9, 1, 7, 3, 5]), 1))

        

        
Sort the list first with sorted(items) (see sorting), or use linear search for unsorted data.

      

      
      

        
Forgetting the +1 / -1 when moving boundaries

        

          
✗ Wrong
low = 0
high = 4
items = [1, 2, 3, 4, 5]
target = 9
while low <= high:
    mid = (low + high) // 2
    if items[mid] < target:
        low = mid
    else:
        high = mid
The loop never ends (infinite loop): when low and high are 3 and 4 and mid is 3, low stays 3 forever.

          
✓ Right
low = 0
high = 4
items = [1, 2, 3, 4, 5]
target = 9
while low <= high:
    mid = (low + high) // 2
    if items[mid] < target:
        low = mid + 1
    else:
        high = mid - 1
print("done")

        

        
Use low = mid + 1 and high = mid - 1, since mid has already been compared.

      

      
    

    

    
    

      
Python Binary Search Program (Iterative and Recursive): questions people ask

      
Why must the list be sorted for binary search?
Binary search discards half of the list based on one comparison, which is only valid if everything left of the middle is smaller and everything right of it is larger. On an unsorted list that assumption is false and the result is wrong.
What is the time complexity of binary search?
Binary search is O(log n) because the search range is halved every step. Searching 1,000,000 sorted items takes at most about 20 comparisons.
Is there a built-in binary search in Python?
Yes: the bisect module in the standard library. bisect_left() and bisect_right() find the insertion point in a sorted list using binary search.

    

    

    
    

      
Keep learning

      
Step-by-step lessons:
Python while LoopsPython ListsPython Sorting

      
Related:
Python Program for Linear Search (with Examples)Python sorted() FunctionPython Bubble Sort Program (with Explanation)Python Recursion

      
More in algorithms:
Python Program for Linear Search (with Examples)Python Bubble Sort Program (with Explanation)Python Selection Sort Program (with Explanation)Python Tower of Hanoi Program (Recursion Explained) See all →