DSA Series Day 23 Binary Search in Java, Python and Rust

DSA Series Day 23: Binary Search in Java, Python and Rust

SeriesDay 23
ChapterBinary Search
TimeO(log n)
SpaceO(1)

Welcome to Day 23 of the Tekraze DSA series. We finished linked lists last time, so today we open a brand new chapter with Binary Search. It is the simplest problem in this chapter, but almost every hard search question later on is built on top of it. Get this one solid and the rest of the chapter feels a lot lighter.

What is the Binary Search problem?

You get an array of integers nums sorted in ascending order and an integer target. Return the index of target if it exists, otherwise return -1. Your solution must run in O(log n) time.

Example 1
Input:  nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4
Example 2
Input:  nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1

How should you think about it in plain words?

Think of guessing a number between 1 and 100 when someone tells you higher or lower. You never guess 1, 2, 3 in order. You guess 50, then 75 or 25, and each answer throws away half of what is left.

A sorted array gives us that same higher or lower signal. Look at the middle value, and you instantly know which half can’t hold the target.

Binary search explained as a higher or lower guessing game that halves the range each time
DSA Series Day 23: Binary Search in Java, Python and Rust 7

What does the brute force approach look like?

Walk through the array from left to right and stop when you see the target.

brute_force.py
def search_brute(nums, target):
    for i, x in enumerate(nums):
        if x == target:
            return i
    return -1
TimeO(n)
SpaceO(1)

It works, but it ignores the fact that the array is sorted, and the problem asks for O(log n).

How do we get the optimal solution?

Keep two pointers, left at the start and right at the end. While the range is not empty, pick mid in the middle.

Equal? Done.If nums[mid] equals the target, return mid.
Smaller? Go right.The target can only be on the right, so move left to mid + 1.
Bigger? Go left.Move right to mid - 1.
Pointers cross?The target is not there, so return -1.
Step 1: left = 0, right = 5, mid = 2. nums[2] = 3 is smaller than 9, so move left to mid + 1.
0-1L
10
23M
35
49
512R
Step 2: left = 3, right = 5, mid = 4. nums[4] = 9 equals the target, so return 4.
0-1
10
23
35L
49M ✓
512R
TimeO(log n)
SpaceO(1)

Time is O(log n) because the range halves on every step, so a million items need only about 20 checks. Space is O(1) since we keep just three indexes.

Also Read: If log n still feels fuzzy, our Big O helper post on time and space complexity explains it with simple charts.
JAVA

Java solution

Solution.java
public class Solution {
    public static int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2; // avoids int overflow
            if (nums[mid] == target) return mid;
            if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }
    public static void main(String[] args) {
        int[][] arrs = {{-1, 0, 3, 5, 9, 12}, {-1, 0, 3, 5, 9, 12}, {5}, {5}, {}, {1, 3}, {1, 3}};
        int[] targets = {9, 2, 5, -5, 1, 1, 3};
        int[] expected = {4, -1, 0, -1, -1, 0, 1};
        for (int i = 0; i < arrs.length; i++) {
            int got = search(arrs[i], targets[i]);
            if (got != expected[i]) throw new AssertionError("case " + i + " got " + got);
        }
        System.out.println("Java: all tests passed");
    }
}
PYTHON

Python solution

solution.py
def search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1
if __name__ == "__main__":
    cases = [([-1, 0, 3, 5, 9, 12], 9, 4), ([-1, 0, 3, 5, 9, 12], 2, -1),
             ([5], 5, 0), ([5], -5, -1), ([], 1, -1), ([1, 3], 1, 0), ([1, 3], 3, 1)]
    for nums, target, want in cases:
        assert search(nums, target) == want, (nums, target)
    print("Python: all tests passed")
RUST

Rust solution

Indexes in Rust are usize, so mid - 1 could underflow when mid is zero. The Rust version uses a half open range where right points one past the end, which keeps every index safe and needs no casting tricks.

main.rs
pub fn search(nums: &[i32], target: i32) -> i32 {
    // Half-open range [left, right) so right never goes below zero.
    let (mut left, mut right) = (0usize, nums.len());
    while left < right {
        let mid = left + (right - left) / 2;
        if nums[mid] == target {
            return mid as i32;
        } else if nums[mid] < target {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    -1
}
fn main() {
    let cases: Vec<(Vec<i32>, i32, i32)> = vec![
        (vec![-1, 0, 3, 5, 9, 12], 9, 4),
        (vec![-1, 0, 3, 5, 9, 12], 2, -1),
        (vec![5], 5, 0),
        (vec![5], -5, -1),
        (vec![], 1, -1),
        (vec![1, 3], 1, 0),
        (vec![1, 3], 3, 1),
    ];
    for (nums, target, want) in cases {
        assert_eq!(search(&nums, target), want);
    }
    println!("Rust: all tests passed");
}

All three programs ran a found target, a missing target, a single element hit and miss, an empty array and both ends of a two element array. Every check passed in Java, Python and Rust.

Binary search solutions in Java, Python and Rust with all tests passed
DSA Series Day 23: Binary Search in Java, Python and Rust 8

What are the tips and tricks for an easy solution?

🔍

Spot the pattern

Sorted input plus a request for O(log n) almost always means binary search.

📐

Pick one template

Either closed range with left <= right and right = mid - 1, or half open with left < right and right = mid. Mixing them is where most bugs come from.

🛡️

Safe middle

Write left + (right - left) / 2 in Java and C++ so a huge array never overflows the sum.

📉

Always shrink the range

Every branch must move left or right past mid, or the loop can spin forever.

🧪

Edge cases

Test an empty array, one element, the target at index 0, the target at the last index and a target smaller or bigger than everything.

🎤

Interview tip

Say the loop invariant out loud, for example the target, if present, is always inside left to right. It proves your code is correct and calms down any follow up questions.

What are the common mistakes people make?

⚠️

Skipped element

Writing left < right with a closed range and skipping the last remaining element.

♾️

Infinite loop

Setting left = mid instead of mid + 1, which causes an infinite loop on two elements.

💥

Overflow

Computing (left + right) / 2 in a language where the sum can overflow.

🔀

Unsorted input

Running binary search on an array that is not sorted.

↩️

Wrong return

Returning left or mid after the loop instead of -1 when the value is missing.

Binary search edge cases checklist covering empty array, single element and both ends
DSA Series Day 23: Binary Search in Java, Python and Rust 9

Where is this pattern used in the real world?

🗄️

Databases

Databases use the same halving idea inside B tree indexes to find rows fast.

🐛

git bisect

git bisect binary searches your commit history to find the commit that broke a build.

📚

Standard libraries

Java’s Arrays.binarySearch, Python’s bisect module and Rust’s slice::binary_search are this exact algorithm.

🖥️

Search on answers

Teams even binary search on answers, like finding the smallest server count that keeps latency under a limit.

Which earlier posts in the series should you read?

Also Read: Keep our data structures cheat sheet handy for a quick look at why sorted arrays make searching so fast. Then test yourself on LeetCode’s Binary Search problem.

Frequently asked questions

What is binary search?

Binary search finds a value in a sorted array by checking the middle element and throwing away the half that cannot contain the target, repeating until it is found or the range is empty.

What is the time complexity of binary search?

Binary search runs in O(log n) time and O(1) extra space for the iterative version, because the search range halves on every step.

Does binary search work on unsorted arrays?

No. It relies on the array being sorted so that one comparison tells you which half to drop. Sort first or use a linear scan or hash set instead.

Why use left + (right – left) / 2 for the middle?

In languages with fixed size integers like Java, left + right can overflow for very large arrays, a bug Joshua Bloch described in this Google Research post. Subtracting first keeps the value in range.

Should I write binary search iteratively or recursively?

Iterative is usually preferred in interviews because it uses O(1) space and avoids recursion depth limits, while recursive uses O(log n) stack space.

Content Protection by DMCA.com
Spread the love
Scroll to Top
×