Binary search

Binary search depends on sorted input

Binary search uses ordering information to discard a large part of the remaining search space after each comparison. The array must already be sorted under the same comparison rule used by the search. The ordering precondition is part of the algorithm’s correctness, not an optional performance hint. This helper returns an index for a found target and negative one for absence. It does not sort its input, report an insertion position, or promise the first occurrence when equal values appear several times.

Find seven, then establish that four is absent

For target seven, the initial midpoint is index two, whose value is five. Seven must lie to its right, so low becomes three. The next midpoint is index three and contains seven, producing result 3. For target four, five is too large, then one and three are too small in the progressively narrowed interval. Eventually low exceeds high and the helper returns -1. The first output is a zero-based index, not the found value seven; the second is the method’s explicit absence marker.

var middle = low + (high - low) / 2;

Maintain a closed interval of possible answers

The helper uses a closed interval from low through high, initially zero through Length minus one. When the midpoint is too small, positions through that midpoint cannot contain the target, so low advances past it. When it is too large, high moves before it. Each update both preserves any possible answer and shrinks the interval. The midpoint formula avoids directly adding two potentially large indices. An empty array starts with high negative one, so the loop correctly exits before reading an element.

A matching index is not automatically a boundary result

With repeated values, this method returns whichever matching midpoint it encounters. It does not establish the first or last duplicate. If the application needs a lower-bound insertion position, duplicate count, or stable boundary before equal values, use a separate algorithm with that contract. Another mistake is applying binary search to unsorted input because a few examples still find their target. Accidental success does not restore the ordering inference that justifies discarding half of the candidates.

Practice: cover the index and absence cases

Test the first and last stored values, a target below all values, a target above all values, an empty array, and a single-element array. Write each expected index or absence result before running. Then add repeated threes to a separate sorted input and verify that any returned index actually contains three, without demanding the first occurrence from a method that never promised it. These cases expose interval and return-contract mistakes more effectively than repeating one successful middle lookup.

• Check the found value through the returned index only after confirming that the result is nonnegative.
• Do not treat negative one as a valid array position or reinterpret it as an insertion boundary.

Practice: count eliminated candidates rather than milliseconds

For an independent experiment, add a comparison counter and use a sorted array of thirty-one even values from zero through sixty. Search for forty-two and then forty-three, predicting a found index of twenty-one and an absent result respectively. Trace the low-high interval at each step and explain which candidates were ruled out. Compare the number of inspected elements with a simple linear scan, but do not turn one tiny stopwatch run into a claim about real application performance.

• Reset instrumentation between calls so a reported count belongs to one search.
• Include any required sorting cost when deciding whether repeated binary lookup is appropriate for a larger workflow.

Prove that every discarded region is impossible

The essential reasoning is that a sorted order makes one side of the midpoint impossible after a comparison. A correct implementation must preserve possible answers, make progress, and stop before indexing an empty interval. Tests should cover boundaries and duplicates according to the helper’s actual promise. The local integer-array example runs through ordinary managed code in this browser runtime; its usefulness comes from a clear invariant and return contract, not from any desktop-specific facility or a universal claim that binary search is best for every collection.

• Baseline returns index 3 for seven and -1 for four.
• Input must be sorted ascending under the comparison used by the loop.
• Finding an arbitrary match differs from finding the first duplicate or an insertion boundary.