This week, let's take a look at the Fix Point problem from binarysearch.com!
The Problem
Fixed Point asks us to write a function that takes in a sorted array and returns the minimum index, or i, that is equal to the value at that index. If there is no such value, then return -1. So if the array is [-1, 0, 2, 3], the return value would be 2 — the first index that equals the value. There are some constraints, but we’ll get to that in a second.
Solution 1
Taking this problem at face value, it’s fairly simple. All we need is a simple for loop that checks if nums[i] === i, and if there isn’t then simply return -1. Add in a base case for coverage, and we have something like this:
Simple enough. However, with that for loop performing a linear search of nums array, we are using a brute force method and running at sub-optimal time complexity. This algorithm runs at O(n), meaning as the input increases, so does the time it takes to solve. And now, let's take a look at the prompt as given:
Firstly, n can be as large as 100,000 elements, which means our linear algorithm will be taking it’s sweet time at that point. Secondly, they ask if we can find a way for this to run in O(log n) time. Now… we need to find a specific number in a sorted array in O(log n) time… if only there was a way to search a numerically sorted array in that time. Joking aside, binary search is a great way to tackle this problem.
Binary Search Solution
It needs a little tweaking to account for the return of -1 if no number is found that fits the asking criteria. Eventually, we get something that looks like this:
We define a starting point and an end, and then inside of a while loop, we define mid as the median, rounded down. Then we check to see if that midpoint, or index, actually points to the same value. If so, we assign min to this mid value, and then reassign end to mid-1, so that we are only checking indexes lower than this one that might become a new minimum. If mid doesn’t point to the same value as its index, then we check to see if what it points to is larger or smaller than mid. If it’s smaller, we know because it’s sorted, we need to move our starting point up further and check again. If it’s larger, we set reassign end to mid-1 and check again. Our loop eventually gets broken when our starting point is larger than our endpoint. Regardless if min ever gets reassigned, we have it initialized at -1 so all we need to do is simply return min at the end.
I hope this helps seeing how binary search can be used in the wild to optimize our times!
