搜索

Linear Search

The linear search is just going from the first element to a last element of your data, stopping if you find the element you're looking for. In the worst case, if you have $n$ terms to search through, so this algorithm runs in $O(n)$.

Binary Search

Binary search is a great search that works when your data is already in order. Think of it as that game where Player 1 thinks of a number, and Player 2 must try to guess that number after Player 1 says lower or higher. Well binary search does just that.

Since the data is already in order, we will know when we have passed an element. So if we have $n$ elements, look at element $n/2$. If it is too high, then perform the algorithm in the interval $[1,n/2)$. If it is too low, then perform the algorithm in the interval $(n/2,n]$.

Say we wanted to find the index of the element $20$ in the array $A=[1,2,4,5,8,10,16,20,24,30,32,33]$. Since there are $12$ elements, look at the $6$th element, $10$. This is too low, so look in the interval $[7,12]$. Check the middle term, the $9$th term, which is $24$. This is too high again, so check in the interval $[7,8]$. Check the middle term, the $7$th term. This is too low again, so check the $8$th term and we win.

The binary search algorithm runs in $O(\log n)$ since if you have $n=2^k$ elements, it will need to halve $k=\log_2n$ times to terminate. (By the way: $O(\log n)$ is really good! It certainly pays off to keep your data sorted if you plan on searching in it a lot.)