Solving Fixed Point Algo in JS

This week, let's take a look at the Fix Point problem from binarysearch.com!

The Problem

Solution 1

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

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!

California native, living in NYC. Early Career Software Engineer.