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.
Input: nums = [-1, 0, 3, 5, 9, 12], target = 9 Output: 4
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.

What does the brute force approach look like?
Walk through the array from left to right and stop when you see the target.
def search_brute(nums, target):
for i, x in enumerate(nums):
if x == target:
return i
return -1It 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.
nums[mid] equals the target, return mid.left to mid + 1.right to mid - 1.-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.
Java solution
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 solution
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 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.
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.

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.

Where is this pattern used in the real world?
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?
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.





