Linear search (4)
Analysis (counting comparisons):
Let n = right – left + 1 be the length of the array.
If the search is unsuccessful, step 1.1 is repeated n times.
If the search is successful, step 1.1 is repeated between 1 and n times.
Average no. of comparisons = (n + 1)/2
In either case, time complexity is O(n).