Indian Computing Olympiad

Searching

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₂N. We will only deal with logarithms to the base to, so we just write log N intead of log₂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)

Some problems based on binary search

• Wires and Switches (IOI 1995)
• Rods (IOI 2002)
• Off with the Head (IOITC 2003)
• Aliens (IOI 2007)
• Post Election Transfers (IOITC 2006)