The Binary Search Mental Model

There are new variations of coding problems that pop up daily. Though practice does make perfect, you'll never be able to memorize or grind enough if the strategy is to only solve as many problems as possible. You will go crazy, unless you like that kinda thing. It's also not a good approach if you're looking to optimize your understanding of algorithms.

Just like certain types of data work best with certain data structures, most problems fit in specific categories. As I aim to grow in my career, I've seen my share of failures and success stories. One of my early failures was not having a concrete strategy for learning Data Structures and Algorithms. You(I) can be as consistent as you want, but if there isn't a plan in place to approach the problem and recognize the problem type in the wild, it would be a good idea to revisit your strategy.

Pattern 1: The Binary Search

Understanding the Process

The Process

1. Grab 2 Pointers. One points to the beginning index of your array, and the other pointer is directed at the last index of your array.

     l = 0
     r = len(arr) - 1

1. With us having the start and stop values available, we can find the middle index of our list/array handing. Let's now find the middle value.

    middleIdx = (l + r) / 2

1. Check if the value in the middle index position of the array is equal to the array. Return the index of that value if so.

    if key == arr[middleIdx]:
        return middleIdx

1. If the key is > than the value at arr[middleIdx], this means that the key is greater than all of the numbers before the middleIdx. This means that we can shorten our array a bit and move our starting pointer to l = middleIdx + 1
2. if the key is less than the value at arr[middleIdx, this means that the key is less than all of the numbers after the middleIdx. This means that we can shorten our array a bit and move our ending pointer to r = middleIdx - 1

Steps 2 through 4 will continue to be repeated to get new ranges for our starting/l and ending/r pointers. If the start ever becomes greater than the end, the key is unable to find the key in the array, leading us to simply return -1.

What if the array is sorted in descending order?

Step 4 would be where the changes are made.

If key > than the value at arr[middleIdx]:

• key > all numbers aftere the middleIdx
• reduce the area to search by resetting the end to end = middleIdx - 1

If key < than the value at arr[middleIdx]:

• key < all numbers aftere the middleIdx
• reduce the area to search by resetting the end to start = middleIdx + 1

How to decipher order of sorted array?

• Compare the numbers pointed out the the start and end pointers
• If the arr[l] < arr[r], this means the order is ASCENDING
• If the arr[l] > arr[r], this means the order is DESCENDING

Compete Code Example

    def binarySearch(arr, key):
        l, r = 0, len(arr) - 1
        isAscending = arr[l] < arr[r]
        while l <= r:
            middleIdxVal = (l + r) // 2

            if key == arr[middleIdxVal]:
                return middleIdxVal

            if isAscending:
                if key > arr[middleIdxVal]:
                    l = middleIdxVal + 1
                else:
                    r = middleIdxVal - 1
            else:
                if key > arr[middleIdxVal]:
                    r = middleIdxVal - 1
                else:
                    l = middleIdxVal + 1

        return -1

    print(binary_search([1, 2, 3, 4, 5, 6, 7], 5))

Code Example Explained

Problem Statement We are given an array of numbers and a key that we are searching for in the array. If we are able to find that key in the array, return the index of it. If we are unable to locate the key in our array, we want to return -1.

Test Case Array = [1,2,3,4,5,6,7] | Key = 5

• Line 1: We start by creating 2 Pointers that will adjust as we search for the key. L and R are what I name them, but they are also commonly called the start and end. L is set to the first index of the input array, and R is set to the last index of the array.
• Line 2: To figure out the order of our sorted input array, we create a variable that will return a boolean. If True, the array is sorted in ascending order. If False, it is sorted in descending order.
• Line 3: With our 2 pointers available, we can now iterate through the array using a while loop. As long as the l pointer value is less than or equal to the r pointer, we are within the bounds of the input array.
• Line 4: At this point, we set the current middle index in a variable. This is calculated by summing the left and right pointers together, and then dividing that sum by 2.
• Line 5: With the middle index obtained in line 4, we can now compare that value in our array against the input key. If they match, we want to return the middle index variable.

Anything past line 5 is ran if we haven't yet found the key in our array.

• Line 6: We utilize the isAscending variable to determine which conditions to use. If the variable returns true, the array is sorted in ascending order, meaning we will use the first set of if/else conditions. Otherwise, the variable returned False, meaning we will need to use the second set of if/else conditions.
• Lines 7- 10: If the input key is greater than the value at the position in the array of the middle index, we shift the l/start pointer to the middle index + 1. Else, the key is less than the value at the position in the array of the middle index, leading us to shifting the r/ending pointer to the middle index - 1.
• Lines 11-15: Else, we have found our array to be sorted in descending order, meaning, we need to use the second set of if/else conditions.If the input key is greater than the value at the position in the array of the middle index, we shift the r/ending pointer to the middle index - 1. Else, the key is less than the value at the position in the array of the middle index, leading us to shifting the l/starting pointer to the middle index + 1.
• Line 16: If we make it to line 16, that means we were not successful in finding the key in the array, therefore returning -1.

Code Example 2 - For Loop

    def binarySearchOne(arr, key):
    l = 0
    isAscending = arr[l] < arr[-1]
    for r in range(0, len(arr)):
        middleIdx = (l + r) // 2
        if key == arr[middleIdx]:
            return middleIdx

        if isAscending:
            if key > arr[middleIdx]:
                l = middleIdx + 1
            else:
                r = middleIdx - 1
        else:
            if key > arr[middleIdx]:
                r = middleIdx - 1
            else:
                l = middleIdx + 1
    return -1

print(binarySearchOne([4, 6, 10], 10))

Code Example Explained

Problem Statement We are given an array of numbers and a key that we are searching for in the array. If we are able to find that key in the array, return the index of it. If we are unable to locate the key in our array, we want to return -1.

Test Case Array = [4,6,10] | Key = 10

• Line 1: We start by creating a pointer that will adjust as we search for the key. L will be the variable name, but it is also commonly called the start. L is set to the first index of the input array.

Our second pointer will be a part of our for loop, and will be the same R pointer as used in the while loop.

• Line 2: To figure out the order of our sorted input array, we create a variable that will return a boolean. If True, the array is sorted in ascending order. If False, it is sorted in descending order.
• Line 3: With our 2 pointers available, we can now iterate through the array using a while loop. As long as the l pointer value is less than or equal to the r pointer, we are within the bounds of the input array.
• Line 4: At this point, we set the current middle index in a variable. This is calculated by summing the left and right pointers together, and then dividing that sum by 2.
• Line 5: With the middle index obtained in line 4, we can now compare that value in our array against the input key. If they match, we want to return the middle index variable.

Anything past line 5 is ran if we haven't yet found the key in our array.

• Line 6: We utilize the isAscending variable to determine which conditions to use. If the variable returns true, the array is sorted in ascending order, meaning we will use the first set of if/else conditions. Otherwise, the variable returned False, meaning we will need to use the second set of if/else conditions.
• Lines 7- 10: If the input key is greater than the value at the position in the array of the middle index, we shift the l/start pointer to the middle index + 1. Else, the key is less than the value at the position in the array of the middle index, leading us to shifting the r/ending pointer to the middle index - 1.
• Lines 11-15: Else, we have found our array to be sorted in descending order, meaning, we need to use the second set of if/else conditions.If the input key is greater than the value at the position in the array of the middle index, we shift the r/ending pointer to the middle index - 1. Else, the key is less than the value at the position in the array of the middle index, leading us to shifting the l/starting pointer to the middle index + 1.
• Line 16: If we make it to line 16, that means we were not successful in finding the key in the array, therefore returning -1.