Given a list of unique integers nums sorted in ascending order, return the minimum i such that nums[i] == i. If there’s no solution, return -1.
This should be done in
time.
Constraints
n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [-5, -2, 0, 3, 4]
Output
3
Explanation
Both nums[3] == 3 and nums[4] == 4 but 3 is smaller.Example 2
Input
nums = [-5, -4, 0]
Output
-1
Explanation
There’s no i such that nums[i] = i.
Simple Bruteforce Algorithm (Linear Search) to Find Fixed Point
Intuitively, we can do a linear search algorithm to check from the begining. This takes O(N) time and O(1) constant space.
C++ algorithm to find the fixed point in linear time:
1 2 3 4 5 6 7 | int findFixedPoint(vector<int>& nums) { if (nums.empty()) return -1; for (int i = 0; i < nums.size(); ++ i) { if (nums[i] == i) return i; } return -1; } |
int findFixedPoint(vector<int>& nums) {
if (nums.empty()) return -1;
for (int i = 0; i < nums.size(); ++ i) {
if (nums[i] == i) return i;
}
return -1;
}Python algorithm to find the fixed point also in linear time with the help of enumerate function:
1 2 3 4 5 6 | class Solution: def findFixedPoint(self, nums): for i, v in enumerate(nums): if i == v: return i return -1 |
class Solution:
def findFixedPoint(self, nums):
for i, v in enumerate(nums):
if i == v:
return i
return -1Binary Search Algorithm to Find Fixed Point
Since the array is already sorted, we can perform a binary search algorithm. When nums[mid] is mid, we also need to search the left side. If nums[mid] is larger than mid, we know the answer should be in the lower half (the uppoer half will not satisfy the requirement). If nums[mid] is smaller, the answer is in the upperbound.
C++ Binary Search to Find the Fixed Point.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | int findFixedPoint(vector<int>& nums) { if (nums.empty()) return -1; int lo = 0, hi = static_cast<int>(nums.size()) - 1; int ans = INT_MAX; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (nums[mid] == mid) { ans = mid; hi = mid - 1; } else if (nums[mid] > mid) { hi = mid - 1; } else { lo = mid + 1; } } return ans == INT_MAX ? -1 : ans; } |
int findFixedPoint(vector<int>& nums) {
if (nums.empty()) return -1;
int lo = 0, hi = static_cast<int>(nums.size()) - 1;
int ans = INT_MAX;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == mid) {
ans = mid;
hi = mid - 1;
} else if (nums[mid] > mid) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
return ans == INT_MAX ? -1 : ans;
}Python algorithm of Binary Search to Find the Fix Point.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | class Solution: def findFixedPoint(self, nums): if len(nums) == 0: return -1 left = 0 right = len(nums) - 1 ans = float("inf") while left <= right: mid = left + (right - left) // 2 if nums[mid] < mid: left = mid + 1 elif nums[mid] > mid: right = mid - 1 else: ans = mid right = mid - 1 if ans == float("inf"): return -1 return ans |
class Solution:
def findFixedPoint(self, nums):
if len(nums) == 0:
return -1
left = 0
right = len(nums) - 1
ans = float("inf")
while left <= right:
mid = left + (right - left) // 2
if nums[mid] < mid:
left = mid + 1
elif nums[mid] > mid:
right = mid - 1
else:
ans = mid
right = mid - 1
if ans == float("inf"):
return -1
return ansBoth implementations run at O(LogN) logarithm time. Space complexity is O(1).
–EOF (The Ultimate Computing & Technology Blog)
loading...
Last Post: Algorithms to Compute the Length of a Linked List
Next Post: Teaching Kids Programming - Reverse a Linked List using Recursion and Iterative Algorithms
