Sorted arrays · Joshua Wong

What sorting gives us

An array is sorted in ascending order when each value is no greater than the next. Equal values are allowed. For an array $a$ of length $n$ , the condition is

a_i \le a_{i+1} \quad \text{for } 0 \le i < n-1.

Consider [2, 5, 8, 12, 16, 23, 38]. Once you know that the middle value is 12, you also know that nothing to its left can be 23. Sorting turns one comparison into information about many values.

Two ways to search

Method	Requirement	Worst-case comparisons	Useful when
Linear search	None	$O(n)$	You have an unsorted collection or only a few items
Binary search	Sorted random-access sequence	$O(\log n)$	You repeatedly search a sorted array

Sorting itself has a cost. Sorting an entire array just to answer one search query is not automatically faster than scanning it once. The benefit depends on how often you search and how often the data changes.

Indices and values

An index is a position; a value is what is stored there. In the example, a[3] is 12. The value 23 sits at index 5.

int[] values = {2, 5, 8, 12, 16, 23, 38};
System.out.println(values[3]); // 12

Check your understanding

If the middle value is 12 and you want 5, which side can you discard?

Show worked solution

Discard the middle value and everything to its right. Every value there is at least 12, so none can equal 5. The remaining candidates are [2, 5, 8].