Easy Searching ⭐ Core Computer Science

Binary Search — O(log n) Implementation in Python, C & JavaScript

Problem Statement

Given a sorted array nums and target, return its index or -1 if not found. Must run in O(log n).

Example

Input: nums = [-1, 0, 3, 5, 9, 12], target = 9

Output: 4

Time Complexity

O(log n)

Space Complexity

O(1)

The Intuition

Two pointers left/right. Check mid. If too small, move left up. If too big, move right down. Stop when left > right.

Solution Code

def search(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = l + (r - l) // 2
        if nums[mid] == target: return mid
        elif nums[mid] < target: l = mid + 1
        else: r = mid - 1
    return -1

int search(int* nums, int n, int target) {
    int l = 0, r = n - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}

function search(nums, target) {
    let l = 0, r = nums.length - 1;
    while (l <= r) {
        const mid = l + Math.floor((r - l) / 2);
        if (nums[mid] === target) return mid;
        else if (nums[mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}

Frequently Asked Questions

Q: Why use l + (r - l) // 2 instead of (l + r) // 2?

In C/Java, (l + r) can overflow a 32-bit integer if both are large. l + (r - l) // 2 is always safe.

Practice These Problems in a Real Curriculum

DoxaTech Hub's 10-month programme covers Data Structures, Algorithms, Python, C, SQL, and Full-Stack Development through 40 weeks of real, graded projects.

Get Started → More Problems