20-CS-122-001 | Computer Science II | Spring 2012 |
---|---|---|
Reorganize a list to find elements efficiently |
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 |