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: binarysearch twopointers threewaycomparison linearscan valuecomparison
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?
Linear Search
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.size1)
if i == arr[i]
return i
end
end
return  1
end

Binary Search
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