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