You can easily and efficiently search through an array of values if they are ordered by using a [[Binary_search_algorithm|Binary Search]]. The idea is to check the middle value and determine if the search value is below or above that point. Either way you can eliminate half the possiblities with one check. Then repeat this procedure with the remaining values, eliminating half with each check until you find the value you are looking for. If N is the number of items in the array, you should be able to find the desired value with log₂N comparisons which is very fast.

Write a function that performs a Binary Search on a list for a specified value. Your main program should fills a list of integers with random values then perform various test searches on the list. Be sure to handle the edge cases where the search value is less than the first value, greater than the last value or if the value is not in the list at all.

Time how long it takes to generate N random integers, sort those N integers and search for those integers N times. Do this for N = 10³, 10⁴, 10⁵, 10⁶ and 10⁷. Then plot the results. Do the curves for generating, sorting and searching have different shapes?

The shape of these curves that describe the behavior of an algorithm as N gets larger are referred to using [[Big O notation]]. Typically algorithms are classified by Big O notations such as `O(1)`, `O(log x)`, `O(x)`, `O(x log x)`, `O(x^2)` or `O(x^3)`. These notations are listed in order of increasingly larger growth as N increases. If we had the choice to choose between two algorithms of `O(log x)` or `O(x)`, we would generally prefer the `O(log x)` since its execution time complexity grows more slowly then does `O(x)`. The most desireable is `O(1)` which is constant time. No matter the size of N, it always takes the same amount of time.

See Quicksort for a sort algorithm you can use for a sort function and LCGPseudorandomGenerator for a random number generator function.