Lesson menuPython TutorialHideShow

Python Tutorial

Binary Search

Search a sorted list in O(log n) by repeatedly halving the range that could contain the target.

← Linear SearchBubble Sort →

The Divide-and-Conquer Idea

Binary search requires sorted data. It compares the target to the middle element: if equal, done; if the target is smaller, discard the right half; if larger, discard the left half. Each step throws away half the remaining elements, giving O(log n) — searching a million items takes about 20 comparisons.

Iterative Implementation

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2       # safe in Python (no overflow)
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1             # target is in the right half
        else:
            high = mid - 1            # target is in the left half
    return -1

data = [11, 12, 22, 25, 34, 64, 90]   # must be sorted!
print(binary_search(data, 25))        # 3
print(binary_search(data, 30))        # -1

Binary search on unsorted data gives wrong answers. Sort first (O(n log n)) — worthwhile only if you search many times.

Recursive Version

def binary_search_rec(arr, target, low, high):
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    if arr[mid] < target:
        return binary_search_rec(arr, target, mid + 1, high)
    return binary_search_rec(arr, target, low, mid - 1)

print(binary_search_rec(data, 64, 0, len(data) - 1))   # 5

Use the Standard Library: bisect

Python's bisect module implements binary search in C. It finds insertion points, which you can use to test membership or keep a list sorted.

import bisect

data = [11, 12, 22, 25, 34, 64, 90]

i = bisect.bisect_left(data, 25)
found = i < len(data) and data[i] == 25
print(i, found)                 # 3 True

bisect.insort(data, 30)         # insert 30 keeping the list sorted
print(data)                     # [11, 12, 22, 25, 30, 34, 64, 90]

Linear vs Binary Search

Linear SearchBinary Search
Data requirementAny orderMust be sorted
TimeO(n)O(log n)
1,000,000 items (worst)~1,000,000 checks~20 checks

Best Practices

  • Ensure the data is sorted before searching.
  • Use low + (high - low) // 2 in languages prone to integer overflow (not needed in Python).
  • Prefer the bisect module in production code.
  • Binary search generalizes: use it to find the first/last item satisfying a condition, or to search an answer space.

Try It Yourself

Exercise 1: Roughly how many comparisons does binary search need for 1,000,000 sorted items?

Show solution

About 20 (log₂ of 1,000,000 ≈ 20).

Exercise 2: Use the bisect module to test if 7 is in a sorted list.

Show solution
import bisect
a = [1, 3, 5, 7, 9]
i = bisect.bisect_left(a, 7)
print(i < len(a) and a[i] == 7)   # True

📘 Real-World Deep Dive

Knowing <strong>DSA Binary Search (algorithms & data structures)</strong> well is what turns algorithms & data structures from a curiosity into a daily tool — you'll reach for it in nearly every real project.

Real-Life Scenario

An end-to-end usage of DSA Binary Search that you'd actually see in a data pipeline or analytics notebook.

Real-Life Example

import bisect
xs = [1, 3, 5, 7, 9, 11, 13]
print("left 5:",  bisect.bisect_left(xs, 5))   # 2
print("right 5:", bisect.bisect_right(xs, 5))  # 3

Expected Output

(see source)

Common mistakes

  • Off-by-one errors in binary-search: the standard idiom is while lo <= hi with mid = (lo + hi) // 2.
  • Recursive algorithms blow the stack for n > ~10⁴; convert to iterative with an explicit stack.
  • Comparison algorithms (sorted(iterable)) are stable by default in Python — surprising for Java/C++ users.
  • Treating DSA Binary Search as a black box without reading the docs — the API has subtle defaults that bite when you scale.

🚀 Performance & Best Practices

  • Use bisect.bisect_left / bisect_right instead of writing your own binary search.
  • Convert a sorted search into a tuple-access pattern with numpy.searchsorted for huge arrays.
  • Use heapq for priority queues instead of maintaining a sorted list manually.
  • When working with algorithms & data structures, prefer vectorised / batched operations over Python loops.

🧪 Try It Yourself

  1. Reproduce the snippet on a representative slice of your own data.
  2. Profile the snippet with cProfile or timeit and find the single biggest improvement.
  3. Generalise the snippet into a small, reusable function you can drop into future projects.

FAQ: Binary Search

Common questions about this page.

What is Binary Search?

Binary Search is a DSA lesson that explains binary search in Python. Search a sorted list in O(log n) by repeatedly halving the range that could contain the target. Copy the samples and run them in the Python editor. It is written for beginners who want a clear definition and working examples.

Should I run binary search examples locally for better learning?

Yes. Use the browser editor on StudyGrid for a quick check, then Download the example and run it on your computer. Local runs show real errors and the real toolchain, which is one of the fastest ways to learn binary search in this DSA Python lesson (Binary Search).

How do I use binary search in Python?

To use binary search in Python, follow the examples on this StudyGrid page. Copy a snippet, run it in the browser, then Download and run it locally for better learning. Change the values and compare the output.

What is the syntax of binary search?

This Binary Search tutorial shows binary search syntax with short Python examples. Use the code blocks in this lesson for the exact statements, then try them in your editor.

Binary Search example for beginners

Yes. This page includes a beginner binary search example you can copy and run. It is designed for searches such as "binary search for beginners", "binary search example", and "how to use binary search".

What are common mistakes with binary search?

Common binary search mistakes include wrong syntax, mixing types, and skipping practice. Work through this DSA chapter in order, run every example, and check the output before moving on.

Why should I learn binary search?

Binary Search is used in real Python work. Learning binary search helps you write clearer programs and continue the DSA tutorial on StudyGrid.

Is Binary Search free to learn online?

Yes. You can learn binary search free on StudyGrid (studygrid.in). This chapter is part of the DSA path and includes examples, syntax, and next-step links.