Algorithms & Sorting

Python Binary Search Implementation

Binary Search finds the target element in a sorted list by repeatedly dividing the search interval in half.

Python Source Code

Editable code sample with line numbers

Python

Expected Output

When this program is compiled and executed, the terminal outputs:

Array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
Target  23 found at index 5
Target  72 found at index 8
Target 100 NOT found in array
Target   2 found at index 0

How the Code Works

Binary search requires the input array to be sorted. At each step, we check the element at index mid. If it equals target, the search succeeds. If target is larger, we eliminate the left half (left = mid + 1). If target is smaller, we eliminate the right half (right = mid - 1). The search space reduces by 50% each iteration.

Time Complexity

O(log N)

Space Complexity

O(1)

Key Takeaways & Best Practices

Input array MUST be sorted beforehand.
Logarithmic time complexity makes searching 1,000,000 items take at most 20 comparisons.

Master Python with ZenCompiler

Practice in our high-performance cloud container IDE with multi-file support, interactive terminal STDIN, real-time memory visualizer, and structured lessons.

Related Python Examples

Math & Numbers

O(√N)

Python Program to Check Prime Number

A prime number is a positive integer greater than 1 that has no positive divisors other than 1 and itself. This example demonstrates an optimized approach checking factors up to √n.

Python Program for Fibonacci Series

The Fibonacci sequence is a series where each number is the sum of the two preceding ones, starting from 0 and 1. Here we implement iterative generation and generator streaming.