Lecture 34

Announcements

CS 4730 (game design) is having a game expo on Friday 18 April from 2:30–4:30 in Rice 120. Play games, be entered in a door prize drawing, and do it all in the name of academia!

Talking Points

Code linear search

Code linear-search-based selection sort

Code binary search

Binary search is easy to describe recursively…

To binary search a part of a list, look in the middle, then either binary search the upper or lower half.

From Class

/*
find the smallest value in the unsorted part of the list
swap that with the first value in the unsorted part of the list
repeat

 346 84732 57 5384 21 58 74 25463 413 5468
^

 21 84732 57 5384 346 58 74 25463 413 5468
   ^

 21 57 84732 5384 346 58 74 25463 413 5468
      ^

 21 57 58 5384 346 84732 74 25463 413 5468
         ^

 21 57 58 74 346 84732 5384 25463 413 5468
            ^
*/
public static void selectionSort(ArrayList<Integer> list) {
    for (int unsortedI = 0; unsortedI < list.size(); unsortedI += 1) {
        int indexOfSmallestValue = unsortedI;
        for(int i = unsortedI; i < list.size(); i+=1) {
            if (list.get(i) < list.get(indexOfSmallestValue)) {
                indexOfSmallestValue = i;
            }
        }
        int small = list.get(indexOfSmallestValue);
        int other = list.get(unsortedI);
        list.set(indexOfSmallestValue, other);
        list.set(unsortedI, small);
    }
}

/*
Binary search
begin, end initially cover the whole list
check the thing halfway between begin and end
if that's the thing we want, return
if that thing is too small, move begining to after it
if that thing is too big, move ending to before it
repeat until begin > end

look for 10 in
0, 1, 1, 1, 2, 4, 4, 6, 6, 8, 9, 12, 67, 2345
[                                           ]

check 6 vs 10
                        [                   ]

check 9 vs 10
                                 [          ]

check 67 vs 10
                                 []

check 12 vs 10
                               ] [

return -1
*/	
public static int binarySearch(ArrayList<Integer> list, int valueWeWant) {
    int begin = 0;
    int end = list.size()-1;
    while (begin <= end) {	
        System.out.println(list+" " + begin + " " + end);
        int halfway = (begin + end)/2;
        int thing = list.get(halfway);
        if (thing == valueWeWant) {
            return halfway; 
        } else if (thing < valueWeWant) {
            begin = halfway + 1; 
        } else {
            end = halfway - 1;
        }
        
    }
    return -1;
}