Search⌘ K
Home
Courses
Data Structures and Algorithms in Python

Find Fixed Number

Explore how to identify a fixed point in a sorted array where the element equals its index. This lesson demonstrates improving from a linear search to an efficient binary search approach, reducing time complexity to O(log n) while maintaining constant space usage.

We'll cover the following...

In this lesson, we will be solving the following problem:

Given an array of nn distinct integers sorted in ascending order, write a function that returns a fixed point in the array. If there is not a fixed point, return None.

A fixed point in an array A is an index i such that A[i] is equal to i.

The naive approach to solving this problem is pretty simple. You iterate through the list and check if each element matches its index. If you find a match, you return that element. Otherwise, you return None if you don’t find a match by the end of the for loop. Have a look at the code below:

Python 3.5
# Time Complexity: O(n)
# Space Complexity: O(1)
def find_fixed_point_linear(A):
    for i in range(len(A)):
        if A[i] == i:
            return A[i]
    return None

As the entire list is traversed once to find the fixed point, spending constant time on each element, the time complexity ...