Linear search (6)
If the (sub)array is known to be sorted, linear search can be speeded up in the unsuccessful case:
To find which (if any) component of the sorted (sub)array a[left…right] equals target:
1. For p = left, …, right, repeat: 1.1. If target equals a[p], terminate with answer p. 1.2. If target is less than a[p], terminate with answer none.2. Terminate with answer none.
However, binary search is much better!