Binary Search

Problem Statement

You're given a list of integers that is already sorted from smallest to largest, with no repeated values, along with a single target integer. Determine whether the target appears anywhere in the list, and if it does, report the position (counting from 0) where it sits. Because the list is guaranteed to be sorted, you can answer this far faster than checking every element one at a time.

Input Format

The input has exactly two lines:

• Line 1: the array, as space-separated integers, sorted in ascending order with no duplicates.
• Line 2: a single integer, the target value to search for.

Output Format

Print a single integer: the 0-based index of the target within the array if it is present, or -1 if the target does not appear anywhere in the array.

Example Walkthrough

Take the second sample: the array 2 4 6 8 10 (indices 0 through 4) with target 5. We start with the whole array in play, so low = 0 and high = 4. We check the middle index, mid = (0 + 4) // 2 = 2, where the array holds 6. Since 6 is greater than the target 5, the target — if it exists at all — must sit to the left of index 2, so we shrink the region to low = 0, high = 1. We check mid = (0 + 1) // 2 = 0, where the array holds 2. Since 2 is less than 5, the target must be further right, so we move low to 1, giving low = 1, high = 1. We check mid = 1, where the array holds 4. That's still less than 5, so we move low to 2. Now low (2) is greater than high (1), meaning the search region has shrunk to nothing — there's no index left to check, so the target isn't in the array. We print -1.

Approach

The straightforward way to solve this is a linear scan: walk through the array from left to right and compare each element to the target, stopping as soon as you find a match. This works on any array, sorted or not, but it costs O(n) time in the worst case, since a target near the end (or a missing target) forces you to look at every single element before you can be sure.

Because this array is sorted, you can do much better. Keep two pointers, low and high, marking the start and end of the region of the array that could still contain the target. Look at the element in the middle of that region: if it equals the target, you're done. If it's smaller than the target, every element at or before that middle position is also too small (the array is sorted ascending), so the entire left half — including the middle — can be discarded, and you continue searching only to the right of it. If it's larger than the target, the entire right half can be discarded instead, and you continue searching only to the left. Either way, one comparison eliminates half of whatever region remained.

This halving is what makes binary search O(log n) instead of O(n): if the array has n elements, you can only cut n in half about log₂(n) times before the region shrinks to nothing. For an array of a million elements, that's around 20 comparisons in the worst case, versus up to a million for a linear scan. The loop ends either when you land on the target (return its index) or when low moves past high, meaning the region is empty and the target isn't present (return -1).

Common Mistakes

• Getting the boundary update wrong. After checking the middle index and ruling it out, the next search region must exclude that index — set low = mid + 1 or high = mid - 1, not low = mid or high = mid. Forgetting the + 1 or - 1 can cause the loop to stop shrinking and never terminate.
• Mixing up which half to keep. If the middle element is smaller than the target, the match (if any) must be to the right, so you keep searching the right half — not the left. Swapping this logic still "looks like" binary search and can even happen to pass a few inputs, but it will consistently search in the wrong direction and give wrong answers on many others.
• Using while low < high and forgetting to check the final remaining index. With a strict < loop condition, the moment low and high become equal the loop exits without ever comparing arr[low] to the target, so a target that happens to be found only at that final position gets missed and -1 is printed incorrectly.