If we want to seach for items in an unsorted list, we have to sequentially scan through all the items. In the worst case, we have to look at the entire list before we find what we are looking for (or conclude that it is not there), so it take time proportional to N to exhaustively search through a list of N items.

If the items are sorted, we use a more efficient method
called *binary search*, that we are all
intuitively familiar with.

Let us assume we are searching for a given number K in a list of numbers.

- Compare K against the middle number in the sorted list. If the middle number is in fact K, we have succeeded in our search.
- Otherwise, let the middle number in the sorted list be M.
- If K < M, we can ignore the second half of the list and search for K in the first half, using the same procedure (compare with the middle number etc).
- Symmetrically, if K > M, we can ignore the first half of the list and search for K in the second half.
- If we reach a situation where the list to be searched is empty, we can be sure that K is not in the list.

How many steps does this take? We begin with a list of
N numbers. Each time we fail to find K, we halve the size
of the list to be searched. We stop halving when the
middle element is the only element in the list—in the
next step, we will have an empty list to search. Thus, in
the worst case, we keep halving N till we reach 1. For
simplicitly, let us assume that N is a power of 2, say
2^{K}. Then, after K steps, we will stop. The
number K is referred to as the logarithm of N to the base
2, written log_{2}N. We will only deal with
logarithms to the base to, so we just write log N
intead of log_{2}N.

In other words, if log N is K, then if we divide N by 2 K times, we will reduce its value to 1. Or, conversely, if we multiply 2 by itself K times, we will cross N. The important point is that log N is much smaller than N, so this is a much more efficient way to search for a value than linearly scanning an unsorted list. For some concrete numerical comparisons, see the page on Sorting.

Video lecture on *Searching in an array*,
NPTEL online course on
Design and Analysis of Algorithms
(Lecture slides)

©IARCS 2012–2016

PÄ›stujeme web | visit: Skluzavky