Unit 10.2 Recursive Searching and Sorting - Teacher notebook • 13 min read

10.2 Binary Search

Binary Search vs Linear Search

target number - 24

intArray - 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40

Popcorn hack:

How many times iterated through for Linear Search?

Answer:

Example of Binary Search with Recursion

public class BinarySearch {
    public static void main(String[] args) {
        int[] intArray = {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40}; // Example array
        int target = 24; // Example target value
        int result = recBinarySearch(intArray, 0, intArray.length - 1, target);

        if (result == -1) {
            System.out.println("Target not found in the array.");
        } else {
            System.out.println("Target found at index: " + result);
        }
    }

    public static int recBinarySearch(int[] intArray, int lowPosition, int highPosition, int target) { //method
        if (lowPosition > highPosition) {
            return -1; // Element not found in the array
        } else {
            int midPosition = (lowPosition + highPosition) / 2;
            if (intArray[midPosition] < target) {
                return recBinarySearch(intArray, midPosition + 1, highPosition, target);
            } else if (intArray[midPosition] > target) {
                return recBinarySearch(intArray, lowPosition, midPosition - 1, target);
            } else {
                return midPosition; // Element found at midPosition
            }
        }
    }
}

BinarySearch.main(null);

Target found at index: 12

Call 1

Index = 0 - 20, midPosition = 10, midPosition value = 20

Since 24 > 20,

then…

lowPosition = midPosition + 1 = 11 highPosition = highPosition = 20

Call 2

Index = 11-20, midPosition index = 15, midPosition value = 30

Since 24 < 30,

then…

lowPosition = lowPosition = 11 high position = midPosition - 1 = 14

Call 3

Index = 11-14, midPosition index = 12, midPosition value = 24

Since 24 = 24,

then…

return midPosition;

In total, our recursive calls to the method 3 times.

Recursive Logic behind Merge Sort

What is Merge Sort? Merge sort is a recursive sorting algorithm that can be used to sort elements in an array or ArrayList

• Follows a divide and conquer approach

Notes:

List: [38,27,43,3,9,82,10] 

sudocode version:
mergeSort(List) {
    mergeSort(left)
    mergeSort(right)
    merge(left & right)

} 

• Must finish call above it in order to finish the call

Call 1:

1. Splitting List into half
2. Left side: [38, 27, 43, 3]
3. Must finish call 1 in order to do the right side and do the merge
4. Recursively calls mergesort and splits the list in half again

Call 2:

1. New Left side List: [38, 27]
2. Method calls are stacking on top of each other

Notes:

1. Element 5 can’t be split into the left or the right, nor can it be merged with itself
2. Consider the left call complete!

Notes:

1. Same thing applies with the right, element 25 can’t be split to the left or the right, nor can it merge with itself.
2. Now we will merge them back in order: [5, 25]

Important concepts:

1. When making new recursive call, we are NOT making a new list, array, or a new set of elements.
2. Basically updating all the way back to the original list

Notes:

1. When merging back together, it will merge back from least to greatest.

Popcorn Hack: What will the final list be?

Answer:

The mergeSort Method

//sudocode
mergeSort(myArray, low, high) {
    if (low < high) {
        middle = (low + high)/2; //find middle
        mergeSort(myArray, low, middle); //make a recursive call from low to middle (look at left hand side)
        mergeSort(myArray, middle + 1, high); //once low is no longer less than high, make a new recursive call (look at right hand side)
        merge (myArray, low, middle, high); //merge back together
    }
}

int [] myArray = {3, 4, 6, 8, 1, 2, 5, 7};

Steps:

1. Split the Array in half
2. Left side: {3, 4, 6, 8}; Right side {1, 2, 5, 7};

1. Compare the first indexes in each individual array (which would be index 0 and index 4)

1. Since 1<3, our new index 0 value would be 1 when we merge the array back together

1. Since 5>3, our new index 2 value would be 3 when we merge the array back together

Popcorn Hack: What will the final array return?

Answer: {}

Wait, but there’s an issue…

• After comparing index 3 and index 7, we then need to compare index 3 and index, but there is no index 8…
• Will recieve an index out of bounds exception.

No worries! Since we are done with the sort, we can just move the rest of the elements to the end of the array because we are already done sorting.

Index 3 will now become index 7.

Hacks:

Create your own merge chart (like the first image in this 10.2 lesson) with your own values from a list, array, or arraylist (doesn’t matter). Explain how recursion works in the merge chat.