Fixed Point in a Given Array in Javascript

A value equal to its index

Photo by Dietmar Ludmann on Unsplash

Approach 1: Linear Search

1. Loop over the array and check if the element is equal to its index in the array
2. If it's true, return the index. Else, return -1

Time Complexity: O(n)

Space Complexity: O(1)

Approach 2: Binary search

1. Find the middle element of the array
2. If the middle element is the fixed point, return the middle index
3. If the index of middle + 1 element ≤ the value at the high index, search on the right side of the middle
4. If the index of middle - 1 element ≥ the value at the low index, search on the left side of the middle
5. Return -1 if no element is found

Time Complexity: O(log n)

Space Complexity: O(1)

Also read,

First and Last Position of an Element in a Sorted Array in JavaScript

Move all negative numbers to the beginning of an array in JavaScript