20-CS-122-001 Computer Science II Spring 2012
Reorganize a list to find elements efficiently

Virtual functions, classes, inheritance, lists, queues, stacks, applications

Given: a list of integers L.
Problem: program a way to find a given integer n efficiently. Output should be the index into L

Idea:
 Sort L. Test for the given number n at the middle of L If n is less than the middle number of L consider the first half of L and repeat Otherwise consider the second half of L and repeat.

Algorithm:
 Open a file and read all the integers into an array L. Sort L using qsort. Create another array called perm and fill it with numbers so that perm[i] is the index of the ith number of the sorted list in L (see the permutation problem). For each number n to find in L do the following: Set pointers low and high to the end elements of L Repeat the following: If low > high Output "No good". If n = L[(high+low)/2] Output perm[(low+high)/2]. If n < L[(high+low)/2] set low = (low+high)/2-1 Otherwise set high = (low+high)/2+1