linear search

int Array- 0 2 4 6 8 10 12 14 16 18 20 22

target 12

with linear search, we just iterate through each value, starting at the start of the list. here, we need 7 iterations to find 4.

iterative binary search

//iterative approach to binary search
// This is a method for performing a binary search on a sorted integer array.
// It returns the index of the target element if found, or -1 if the element is not in the array.
public static int binarySearch(int[] intArray, int lowPosition, int highPosition, int target) {
    int midPosition;

    // Use a while loop to repeatedly divide the search range in half.
    while (lowPosition <= highPosition) {
        // Calculate the middle position of the current search range.
        midPosition = (highPosition + lowPosition) / 2;

        // If the element at the middle position is less than the target,
        // we narrow our search to the right half of the current range.
        if (intArray[midPosition] < target) {
            lowPosition = midPosition + 1;
        }
        // If the element at the middle position is greater than the target,
        // we narrow our search to the left half of the current range.
        else if (intArray[midPosition] > target) {
            highPosition = midPosition - 1;
        }
        // If the element at the middle position is equal to the target,
        // we have found our target, and we return its index.
        else {
            return midPosition;
        }
    }
    
    // If the while loop completes without finding the target, we return -1 to indicate it's not in the array.
    return -1;
}

recursive binary search

public static int recBinarySearch(int[] intArray, int lowPosition, int highPosition, int target) {
    int midPosition;

    // Check if the lower index is greater than the higher index, indicating an empty search range.
    if (lowPosition > highPosition) {
        // If the low index is greater than the high index, the target element is not found.
        return -1;
    } else {
        // Calculate the middle index of the current search range.
        midPosition = (lowPosition + highPosition) / 2;

        // If the element at the middle index is less than the target, search in the right half of the array.
        if (intArray[midPosition] < target) {
            // Recursively call the function with an updated search range (right half).
            return recBinarySearch(intArray, midPosition + 1, highPosition, target);
        }

        // If the element at the middle index is greater than the target, search in the left half of the array.
        if (intArray[midPosition] > target) {
            // Recursively call the function with an updated search range (left half).
            return recBinarySearch(intArray, lowPosition, midPosition - 1, target);
        }

        // If the element at the middle index is equal to the target, we found the target element.
        // Return the index where the target element is found (midPosition).
        return midPosition;
    }
}

tracing through a runthrough

int Array: |0|2|4|6|8|10|12|14|16|18|20|22| Target: 12

recBinarySearch(intArray, 0, 10, 12);

Call 1: Midpoint calculated as (0 + 10) / 2 = 5 The target value 12 is greater than the midpoint value at index 5 (10). So, we narrow our search to values greater than the midpoint.

Call 2: recBinarySearch(intArray, mid1, high, target) Midpoint 1 calculated as (mid + high) / 2 = 7

The midpoint value at index 7 is 14, which is greater than 12, so the next call is between low and mid.

Call 3: Another recursive call finds the midpoint value at index 6, as it’s between low and mid, which is our target number.

If the target does not exist, we would print -1 as the value is not found.

popcorn hack

edit the following code so that running the cell will sort through an array of your creation.

public static int recBinarySearch(int[] intArray, int lowPosition, int highPosition, int target) {
    int midPosition;

    // Check if the lower index is greater than the higher index, indicating an empty search range.
    if (lowPosition > highPosition) {
        // If the low index is greater than the high index, the target element is not found.
        return -1;
    } else {
        // Calculate the middle index of the current search range.
        midPosition = (lowPosition + highPosition) / 2;

        // If the element at the middle index is less than the target, search in the right half of the array.
        if (intArray[midPosition] < target) {
            // Recursively call the function with an updated search range (right half).
            return recBinarySearch(intArray, midPosition + 1, highPosition, target);
        }

        // If the element at the middle index is greater than the target, search in the left half of the array.
        if (intArray[midPosition] > target) {
            // Recursively call the function with an updated search range (left half).
            return recBinarySearch(intArray, lowPosition, midPosition - 1, target);
        }

        // If the element at the middle index is equal to the target, we found the target element.
        // Return the index where the target element is found (midPosition).
        return midPosition;
    }
}

// int[] intArray = {}; // uncomment these lines and fill them in with the info needed for the code to run and find your target.
// recBinarySearch(some code should go here);

9

takeaways

Data must be in sorted order for binary search to work.

The binary search algorithm starts in the middle of the sorted array or arraylist and and eliminates half of the array or arraylist in each iteration until the desired value is found or all elements have been eliminated

Binary search can be more effective than linear search

binary search algorithm can be written linearly or recursively

topic 2 recursive sorting and searching

APPLY RECURSIVE LOGIC TO sort arrays for elements

mergeSort(myList) {
    mergeSort(left)
    mergeSort(right)
}

// left, right merge

example trace (look at the whiteboard, I will draw it out maybe)

Original List: |5|25|8|-9|14|0|-2|2|

The first recursive call begins by splitting the list into the left and right sides: (5, 25, 8, -9).

Another recursive call is made on the left side, which further splits into (5, 25).

The left and right sides are split into individual elements, and the two elements (5 and 25) are merged, resulting in (5, 25).

The current list becomes (5, 25, -9, 8).

The current list is sorted, resulting in (-9, 5, 8, 25).

Current List:

-9 5 8 25 14 0 -2 2

The final left side is sorted, and a recursive call is made for the right side: (14, 0, -2, 2).

The right side is further split into (14, 0).

These two elements (14 and 0) are merged into (0, 14).

The remaining elements (-2 and 2) are merged into (-2, 2).

The right side is now (0, 14, -2, 2).

Current List: |-9|5|8|25|0|14|-2|2|

The left and right sides are finally merged together:

Left: -9, 5, 8, 25

Right: 0, 14, -2, 2

The two merged sides are sorted, resulting in the final sorted list: |-9|0|2|5|8|14|25|

The merge sort process is complete, and the original list is sorted: Sorted List: |-9|0|2|5|8|14|25|

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {5, 25, 8, -9, 14, 0, -2, 2};

        mergeSort(arr); // Call the mergeSort method to sort the 'arr' array.

        System.out.print("Sorted Array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }

    public static void mergeSort(int[] arr) {
        if (arr.length > 1) { // If the array has more than one element, we proceed to sort it.
            int middle = arr.length / 2;

            int[] left = new int[middle];
            for (int i = 0; i < middle; i++) {
                left[i] = arr[i]; // Copy the left half of the array.
            }

            int[] right = new int[arr.length - middle];
            for (int i = middle; i < arr.length; i++) {
                right[i - middle] = arr[i]; // Copy the right half of the array.
            }

            mergeSort(left); // Recursively sort the left half of the array.
            mergeSort(right); // Recursively sort the right half of the array.

            int i = 0, j = 0, k = 0;

            while (i < left.length && j < right.length) {
                if (left[i] < right[j]) {
                    arr[k] = left[i]; // Merge the sorted left and right halves into the original array.
                    i++;
                } else {
                    arr[k] = right[j];
                    j++;
                }
                k++;
            }

            while (i < left.length) {
                arr[k] = left[i]; // If there are remaining elements in the left half, add them to the original array.
                i++;
                k++;
            }

            while (j < right.length) {
                arr[k] = right[j]; // If there are remaining elements in the right half, add them to the original array.
                j++;
                k++;
            }
        }
    }
}

MergeSort.main(null); // Call the main method to start the sorting process.


Sorted Array: -9 -2 0 2 5 8 14 25

TAKEAWAYS

Mergesort is a recursive sorting algorithm that can be used to sort elements in an array or ArrayList

for the AP test, you must remember how it works. remember the left-right merge rule.

hack

Question: what are the usage cases of merge sort? what about usage cases of recursive binary sort? try and come up with a real life scenario for each usage case.