Binary Search Algorithm Explained — How It Works, Why It's Fast, and When to Use It
Every app you've ever used searches for something. Google finds your query in milliseconds. Spotify locates a song among 100 million tracks. Your phone's contacts app jumps straight to 'Zara' without scrolling through 500 names. Speed like that doesn't come from trying harder — it comes from searching smarter. Binary search is one of the foundational reasons software can find things so fast, and understanding it is a rite of passage for every developer.
Why Searching One-by-One Breaks Down (Linear Search vs Binary Search)
Before binary search makes sense, you need to feel the pain it solves. The naive way to search a list is linear search — start at item 1, check it, move to item 2, check it, and keep going until you find your target or run out of items. For a list of 10 things, that's fine. For a list of 1,000,000 things, you could be checking up to one million items. In the absolute worst case, your target is the very last item, or it isn't there at all.
This approach is called O(n) in Big O notation — as the list grows, your work grows at exactly the same rate. Double the data, double the time.
Binary search flips the script. Instead of O(n), it runs in O(log n) time. For a list of 1,000,000 items, binary search needs at most 20 comparisons — not one million. The catch? Your data must be sorted first. That single requirement is what makes the halving trick possible: if your list is sorted, you can always look at the middle and know with certainty which half your target lives in.
public class LinearSearchExample { // Check every element one-by-one until we find the target public static int findWithLinearSearch(int[] sortedScores, int targetScore) { for (int index = 0; index < sortedScores.length; index++) { // Did we find the target at this position? if (sortedScores[index] == targetScore) { return index; // Return the position where it was found } } return -1; // -1 is the convention for "not found" } public static void main(String[] args) { int[] sortedScores = {10, 22, 35, 47, 58, 63, 79, 81, 94, 99}; int targetScore = 79; int result = findWithLinearSearch(sortedScores, targetScore); if (result != -1) { System.out.println("Score " + targetScore + " found at index " + result); System.out.println("Linear search checked " + (result + 1) + " element(s) to get there."); } else { System.out.println("Score " + targetScore + " was not found."); } } }
Linear search checked 7 element(s) to get there.
How Binary Search Actually Works — The Step-by-Step Logic
Here's the core idea, plain and simple. You have a sorted array. You want to find a target value. Binary search maintains two pointers — a left boundary and a right boundary — that represent the section of the array still worth searching. At the start, left is index 0 and right is the last index.
Each round, you calculate the middle index of the current window. You look at the value sitting at that middle index and ask one of three questions: 1. Is the middle value equal to my target? If yes — you're done, return the index. 2. Is the middle value less than my target? Then the target must be in the right half. Move left up to middle + 1. 3. Is the middle value greater than my target? Then the target must be in the left half. Move right down to middle - 1.
You repeat this until either you find the target or left exceeds right (meaning the target isn't in the array at all).
Each iteration eliminates half the remaining candidates. Starting with 1,000,000 items: after step 1 you have 500,000 candidates. After step 2, 250,000. After 20 steps, you're down to 1. That's the magic of logarithms — log base 2 of 1,000,000 is about 20.
public class BinarySearchIterative { /** * Searches for targetScore inside a sorted array using binary search. * Returns the index of the target if found, or -1 if not present. */ public static int binarySearch(int[] sortedScores, int targetScore) { int leftBoundary = 0; // Start of the search window int rightBoundary = sortedScores.length - 1; // End of the search window int stepCount = 0; // Just for demonstration while (leftBoundary <= rightBoundary) { stepCount++; // Calculate midpoint — see the Gotchas section for WHY we write it this way int middleIndex = leftBoundary + (rightBoundary - leftBoundary) / 2; int middleValue = sortedScores[middleIndex]; System.out.println("Step " + stepCount + ": Checking index " + middleIndex + " (value = " + middleValue + ") | window: [" + leftBoundary + ", " + rightBoundary + "]"); if (middleValue == targetScore) { // Bullseye — target is right here System.out.println("Found " + targetScore + " at index " + middleIndex + " in " + stepCount + " step(s).\n"); return middleIndex; } else if (middleValue < targetScore) { // Middle value is too small — target must be in the RIGHT half leftBoundary = middleIndex + 1; } else { // Middle value is too big — target must be in the LEFT half rightBoundary = middleIndex - 1; } } // Left has crossed right — target is not in the array System.out.println(targetScore + " was not found after " + stepCount + " step(s).\n"); return -1; } public static void main(String[] args) { int[] sortedScores = {10, 22, 35, 47, 58, 63, 79, 81, 94, 99}; System.out.println("--- Searching for 63 ---"); binarySearch(sortedScores, 63); System.out.println("--- Searching for 50 (not in array) ---"); binarySearch(sortedScores, 50); System.out.println("--- Searching for 10 (first element) ---"); binarySearch(sortedScores, 10); } }
Step 1: Checking index 4 (value = 58) | window: [0, 9]
Step 2: Checking index 7 (value = 81) | window: [5, 9]
Step 3: Checking index 5 (value = 63) | window: [5, 6]
Found 63 at index 5 in 3 step(s).
--- Searching for 50 (not in array) ---
Step 1: Checking index 4 (value = 58) | window: [0, 9]
Step 2: Checking index 1 (value = 22) | window: [0, 3]
Step 3: Checking index 2 (value = 35) | window: [2, 3]
Step 4: Checking index 3 (value = 47) | window: [3, 3]
50 was not found after 4 step(s).
--- Searching for 10 (first element) ---
Step 1: Checking index 4 (value = 58) | window: [0, 9]
Step 2: Checking index 1 (value = 22) | window: [0, 3]
Step 3: Checking index 0 (value = 10) | window: [0, 0]
Found 10 at index 0 in 3 step(s).
Binary Search the Recursive Way — Same Logic, Different Shape
The iterative version uses a while loop. The recursive version calls itself with a smaller window each time. Both approaches are identical in logic and performance — it's a style choice, though iterative is usually preferred in production because it avoids stack overhead.
In the recursive version, you pass the current left and right boundaries as parameters. When you hit the base case (left > right), you return -1. When you find the target, you return its index. Otherwise you call yourself again with the updated half.
Seeing both versions is valuable because many interview questions ask you to implement one or the other, and understanding recursion here is a perfect stepping stone to harder recursive algorithms like merge sort.
Notice how the recursive version reads almost like the English description of binary search — it's self-documenting. The tradeoff is that each recursive call adds a frame to the call stack. For an array of one million elements, that's at most 20 recursive calls deep, which is perfectly fine — but it's good to be aware of.
public class BinarySearchRecursive { /** * Recursive binary search. * Each call works on a shrinking window defined by leftBoundary and rightBoundary. */ public static int binarySearchRecursive( int[] sortedTemperatures, int targetTemp, int leftBoundary, int rightBoundary) { // Base case: the window is empty — target is not in the array if (leftBoundary > rightBoundary) { return -1; } // Find the midpoint of the current window int middleIndex = leftBoundary + (rightBoundary - leftBoundary) / 2; int middleValue = sortedTemperatures[middleIndex]; if (middleValue == targetTemp) { // Found it — return the position return middleIndex; } else if (middleValue < targetTemp) { // Target is in the right half — recurse with updated left boundary return binarySearchRecursive( sortedTemperatures, targetTemp, middleIndex + 1, rightBoundary); } else { // Target is in the left half — recurse with updated right boundary return binarySearchRecursive( sortedTemperatures, targetTemp, leftBoundary, middleIndex - 1); } } // Convenience wrapper so the caller doesn't need to pass initial boundaries public static int search(int[] sortedTemperatures, int targetTemp) { return binarySearchRecursive( sortedTemperatures, targetTemp, 0, sortedTemperatures.length - 1); } public static void main(String[] args) { int[] weeklyHighTemps = {-5, 0, 3, 7, 12, 18, 21, 26, 30}; int searchTarget = 18; int foundAt = search(weeklyHighTemps, searchTarget); if (foundAt != -1) { System.out.println("Temperature " + searchTarget + "°C found at index " + foundAt); } else { System.out.println("Temperature " + searchTarget + "°C not in records."); } // Try a value that doesn't exist int missingTemp = 15; int missingResult = search(weeklyHighTemps, missingTemp); System.out.println("Temperature " + missingTemp + "°C found at index: " + missingResult + " (−1 means not found)"); } }
Temperature 15°C found at index: -1 (−1 means not found)
Common Mistakes That Break Binary Search (And Exactly How to Fix Them)
Binary search looks simple, but it has a handful of classic traps that catch even experienced developers. The most infamous is the integer overflow bug — it lived undetected in Java's standard library for nearly a decade before being reported. Understanding these mistakes doesn't just help you avoid bugs; it shows interviewers you think carefully about edge cases.
The second most common mistake is applying binary search to unsorted data. The algorithm will run without throwing any errors — it will just silently return the wrong answer. There's no warning, no exception. This is the sneakiest kind of bug.
Third: getting the boundary updates wrong. Using middleIndex instead of middleIndex + 1 when updating the left boundary causes an infinite loop when your window is two elements wide. The loop never terminates because the window never shrinks.
Let's look at each of these concretely in code so you can recognize them on sight.
public class BinarySearchPitfalls { // ============================================================ // MISTAKE 1: Integer overflow when calculating the midpoint // ============================================================ public static int buggyMidpoint(int left, int right) { // WRONG: (left + right) can overflow if both are large integers // e.g. left = 1_500_000_000, right = 1_600_000_000 // Their sum = 3_100_000_000 which exceeds Integer.MAX_VALUE (2_147_483_647) return (left + right) / 2; // <-- DANGER ZONE } public static int safeMidpoint(int left, int right) { // CORRECT: This formula gives the same result but never overflows // because we add a small delta (right - left) to left, not two large numbers return left + (right - left) / 2; // <-- SAFE } // ============================================================ // MISTAKE 2: Infinite loop from wrong boundary update // ============================================================ public static int binarySearchWithInfiniteLoopBug(int[] sorted, int target) { int left = 0; int right = sorted.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (sorted[mid] == target) return mid; else if (sorted[mid] < target) { left = mid; // WRONG: should be mid + 1 // When left = 2, right = 3, mid = 2 // We set left = 2 again — nothing changes — infinite loop! } else { right = mid - 1; } } return -1; } public static int binarySearchFixed(int[] sorted, int target) { int left = 0; int right = sorted.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (sorted[mid] == target) return mid; else if (sorted[mid] < target) { left = mid + 1; // CORRECT: +1 ensures the window always shrinks } else { right = mid - 1; } } return -1; } public static void main(String[] args) { System.out.println("=== Midpoint Calculation ==="); int largeLeft = 1_500_000_000; int largeRight = 1_600_000_000; System.out.println("Buggy midpoint : " + buggyMidpoint(largeLeft, largeRight)); System.out.println("Safe midpoint : " + safeMidpoint(largeLeft, largeRight)); System.out.println("\n=== Fixed Binary Search ==="); int[] prices = {5, 12, 19, 27, 34, 41, 55, 68}; System.out.println("Search for 34: index " + binarySearchFixed(prices, 34)); System.out.println("Search for 99: index " + binarySearchFixed(prices, 99)); } }
Buggy midpoint : -597483648
Safe midpoint : 1550000000
=== Fixed Binary Search ===
Search for 34: index 4
Search for 99: index -1
| Feature / Aspect | Linear Search | Binary Search |
|---|---|---|
| Time complexity (worst case) | O(n) — checks every element | O(log n) — halves the window each step |
| Time complexity (best case) | O(1) — target is first element | O(1) — target is the middle element |
| Requires sorted data? | No — works on any array | Yes — must be sorted first |
| Works on linked lists? | Yes — traverse naturally | Not efficiently — random access needed |
| Steps for 1,000,000 items | Up to 1,000,000 comparisons | At most 20 comparisons |
| Implementation complexity | Trivial — a single for-loop | Moderate — boundary management needed |
| Best use case | Small or unsorted datasets | Large, sorted datasets searched repeatedly |
| Extra memory needed | O(1) iterative | O(1) iterative, O(log n) recursive (stack) |
🎯 Key Takeaways
- Binary search requires a sorted array — running it on unsorted data gives silently wrong answers, no errors thrown.
- Each step eliminates half the remaining candidates — that's why 1,000,000 items need only ~20 comparisons, not 1,000,000.
- Always use
left + (right - left) / 2for the midpoint — the simpler(left + right) / 2overflows for large array indices and is a known real-world bug. - Return -1 when left exceeds right — that crossed-boundary condition is your definitive proof the target isn't in the array.
⚠ Common Mistakes to Avoid
- ✕Mistake 1: Integer overflow in the midpoint formula — Using
(left + right) / 2silently produces a negative number when both left and right are large integers, sending your search to a completely wrong index. Fix it by writingleft + (right - left) / 2instead — mathematically identical result, zero overflow risk. - ✕Mistake 2: Using
left = midinstead ofleft = mid + 1when the target is in the right half — When the search window narrows to two adjacent elements, this causes an infinite loop because the window never actually shrinks. Always writeleft = mid + 1andright = mid - 1to guarantee the window contracts every iteration. - ✕Mistake 3: Running binary search on unsorted data — The algorithm produces no error; it just returns wrong answers or -1 for values that exist. There's no built-in guard. Before calling binary search, ensure your array is sorted with
Arrays.sort(array), or assert the sorted property during development using a validation helper.
Interview Questions on This Topic
- QWhat is the time complexity of binary search and why — can you derive it from first principles rather than just stating O(log n)?
- QWhat happens if the input array contains duplicate values and your target appears multiple times — does standard binary search guarantee finding the leftmost or rightmost occurrence, and how would you modify it to do so?
- QWhy do we write `mid = left + (right - left) / 2` instead of `mid = (left + right) / 2` — what specific scenario makes the simpler formula dangerous?
Frequently Asked Questions
Why does binary search only work on sorted arrays?
Binary search works by eliminating half the remaining elements at each step. It can only do this because in a sorted array, if the middle element is less than your target, you know with certainty the target cannot be in the left half. That certainty disappears the moment the array is unsorted — you'd have no logical basis for discarding either half.
What does binary search return if the target is not in the array?
By convention, binary search returns -1 to signal 'not found'. This works because -1 is never a valid array index. Some implementations throw an exception instead, but returning -1 is the most common pattern in Java and is what Java's built-in Arrays.binarySearch() uses (though it returns a negative insertion point, not exactly -1).
Can you use binary search on a String array or only on numbers?
You can use binary search on any data type that has a defined ordering — strings, objects, custom types — as long as the array is sorted according to that same ordering. In Java, you'd implement the Comparator interface for custom types and pass it to Arrays.binarySearch(). The halving logic stays exactly the same; only the comparison changes.
Written and reviewed by senior developers with real-world experience across enterprise, startup and open-source projects. Every article on TheCodeForge is written to be clear, accurate and genuinely useful — not just SEO filler.