Searching Algorithms

Introduction: 7.5.0

The ability to find a value in a list of data is searching
- The AP Exam covers linear (sequential) search and binary search
Sequential search starts at the first element of an array and looks through all items until it finds the item or gets to the end without finding it
Binary search checks the middle of the dataset to see if it is greater or less than, and eliminates half of the remaining set per cycle
- It can only be used on sorted data

Sequential Search: 7.5.1

Linear search is the only method which can be used on unsorted data
Starts at the first element and walks through the array until it finds the value or gets to the end of the array
- Returns a -1 to show the value doesn’t exist

// arrays
/**
 * Searches through an array to find a value
 * @param elements the array of strings
 * @param term the term to find
 * @return the index of the value; -1 if the value isn't in the array
 */
public int sequentialSearch(String[] elements, String term) {
    for (int i = 0; i < elements.length; i++) {
        if (elements[i].equals(term)) return i;
    }
    // we only get here if none of the elements .equal the term
    return -1;
}

// ArrayLists
/**
 * Searches through a list to find a value
 * @param elements the array of strings
 * @param term the term to find
 * @return the index of the value; -1 if the value isn't in the array
 */
public int sequentialSearch(ArrayList<String> elements, String term) {
    for (int i = 0; i < elements.size(); i++) {
        if (elements.get(i).equals(term)) return i;
    }
    // we only get here if none of the elements .equal the term
    return -1;
}

Binary Search: 7.5.2

Binary search can only be done on a sorted dataset
Keeps dividing the sorted space in half
- Looks for the value in the middle
  - Eliminates half based on whether the value is greater or less than
Loops until the value is found or no values remain
the Middle index is left + right / 2
- Left starts as 0; Right as length - 1

public int binarySearch(int[] elements, int target) {
    int min = 0;
    int max = elements.length - 1;
    while (min <= max) { // while we still have elements to check
        int index = (min + max) / 2;
        if (target < elements[index]) max = index - 1;
        else if (target > elements[index]) min = index + 1;
        else return index;
    }
    return -1;
}

You can use binary search with strings, using .compareTo()
- int compareTo(String other)
  - returns a negative value if the current string is less than the other string, 0 if they have the same characters in the same order, and a positive value if the current string is greater than the other string.

Runtimes: 7.5.3

Runtimes are a measurement of how quickly an algorithm runs
- Binary search is faster than linear search, but it only works on sorted data
- We like to think about worst case behavior

Worst case number of comparisons for different algorithms

N	Linear Search	Binary Search
2	2 comparisons	2 comparisons
4	4	3
8	8	4
16	16	5
100	100	7

Runtimes can be described as mathematical functions. For an array of size n, linear search has a runtime of $ n $ and binary search has a runtime of $ \lfloor \log_2(n) \rfloor $

You don’t need to know the $ \log(n) $ runtime growth for the AP Exam, but you should be able to calculate about how many steps a binary search would take based on how many times you can divide a number in half. You can also start at one and see how many times you double the number before reaching the target.

Summary: 7.5.5

There are starndard algorythms for searching
Sequential/linear search algorithms check each element until the desired value is found, or each element has been checked
binary search algorithms start in the middle of a sorted array
- eliminates half of the array in each iteration until the value is found or we run out of values
Data must be sorted in order to use a binary search
informal runtime comparisons can be made using a number of statements executed