Fixed Point

shitgpt. refer editorial.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution:
    def fixedPoint(self, arr: List[int]) -> int:
        # Initialize the boundary of search space
        left, right = 0, len(arr) - 1

        # Initialize answer to -1, 
        # If no answer is possible, we will return -1
        answer = -1

        # While the boundary size is non zero
        while left <= right:
            # The middle point in the search space
            # To divide the search space into two halves
            mid = (left + right) // 2

            if arr[mid] == mid:
                # We found a possible answer, but keep looking 
                # for a smaller index on the left part
                answer = mid
                right = mid - 1
            elif arr[mid] < mid:
                # No solution possible on left, move to the right half
                left = mid + 1
            else:
                # No solution possible on right, move to the left half
                right = mid - 1

        return answer

title: Fixed Point excerpt: Using binary search to improve time complexity from linear to logarithmic. tags: binary-search two-pointers three-way-comparison linear-scan value-comparison

Given an array of distinct integers arr, where arr is sorted in ascending order, return the smallest index i that satisfies arr[i] == i. If there is no such index, return -1.

Example 1:
Input: arr = [-10,-5,0,3,7]
Output: 3
Explanation: For the given array, arr[0] = -10, arr[1] = -5, arr[2] = 0, arr[3] = 3, thus the output is 3.

Example 2:
Input: arr = [0,2,5,8,17]
Output: 0
Explanation: arr[0] = 0, thus the output is 0.

Example 3:
Input: arr = [-10,-5,3,4,7,9]
Output: -1
Explanation: There is no such i that arr[i] == i, thus the output is -1.

Constraints

  • 1 <= arr.length < 104
  • -109 <= arr[i] <= 109

Follow up: The O(n) solution is very straightforward. Can we do better?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# @param {Integer[]} arr
# @return {Integer}
def fixed_point(arr)
  for i in (0..arr.size-1)
    if i == arr[i]
      return i
    end
  end  

  return - 1
end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# @param {Integer[]} arr
# @return {Integer}
def fixed_point(a)
  result = -1
  left = 0
  right = a.size - 1
  
  while left <= right
    mid = (left + right)/2

    if a[mid] >= mid
      if a[mid] == mid
        result = mid
      end

      right = mid - 1
    else
      left = mid + 1
    end
  end
  
  return result
end

Building Blocks

  • Two Pointers
  • Three Way Comparison
  • Linear Scan
  • Value Comparison