
Problem Statement
In this task, you are provided with a sorted array of unique integers named arr
. The array is sorted in ascending order. Your objective is to find the smallest index i
for which the value of the element at that index equals the index itself (arr[i] == i
). If no such index exists, the function should return -1
. This problem not only tests basic array manipulation but also checks for optimal approaches to searching in a sorted structure.
Examples
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
Approach and Intuition
When approaching the problem where an array is sorted, a binary search methodology becomes an appealing option since it can help reduce the search space significantly. Let's discuss the intuition with reference to the examples provided:
Example 1: Here the array is
[-10, -5, 0, 3, 7]
. A simple iteration from the start would eventually get us to the point where the index 3 contains the value 3 (arr[3] == 3
). This situation is straightforward because the binary search will efficiently find this point since we continuously narrow our search to wherearr[i]
can potentially be equal toi
.Example 2: This example comprises a first element where the index and the value are the same (
arr[0] = 0
). This case highlights a scenario that can be quickly identified even in the first check of our binary search process.Example 3: This situation with
[-10, -5, 3, 4, 7, 9]
demonstrates the case where no index satisfies the condition. The smart application of binary search allows us to discern that there is no solution faster than comparing each element sequentially.
Steps Employed in Binary Search Approach:
- Set initial boundary conditions:
left
to 0 andright
tolen(arr) - 1
. - Loop while
left
is less than or equal toright
:- Calculate the middle index:
mid = (left + right) // 2
. - If
arr[mid] == mid
, then this might be our answer, but we continue searching to the left to find a potentially smaller index that also satisfies the condition. - If
arr[mid] < mid
, then any potentialarr[i] == i
must be to the right, so setleft
tomid + 1
. - Conversely, if
arr[mid] > mid
, we check to the left by settingright
tomid - 1
.
- Calculate the middle index:
- If we exit the loop without finding any such index, return
-1
.
Using this method allows us to optimize our search process down to a log-scaled time complexity, leveraging the sorted nature of the array.
Solutions
- C++
- Java
- Python
class Solution {
public:
int findFixedPoint(vector<int>& data) {
int start = 0, end = data.size() - 1;
int result = -1;
while (start <= end) {
int middle = start + (end - start) / 2;
if (data[middle] == middle) {
result = middle;
end = middle - 1;
} else if (data[middle] < middle) {
start = middle + 1;
} else {
end = middle - 1;
}
}
return result;
}
};
The solution provided implements a method to find a "fixed point" in an array using the binary search algorithm. A fixed point in an array is an index i
such that data[i]
is equal to i
.
- Initialize
start
to 0 andend
to the last index ofdata
. - Initialize
result
to -1 to represent the absence of a fixed point initially. - Use a
while
loop to conduct the binary search as long asstart
is less than or equal toend
:- Calculate the middle index
middle
. - Check if the element at this middle index is the same as its index. If true, store this index in
result
and narrow the search to the left half to find the smallest fixed point (if any). - If the middle element is less than its index, move the start index to
middle + 1
, shifting the search range to the right. - If the middle element is greater than its index, update the end index to
middle - 1
, focusing the search on the left part.
- Calculate the middle index
- At the end of the loop, return
result
. If a fixed point exists,result
will contain the smallest index that satisfies the fixed point condition. Otherwise, it will return -1, indicating no fixed point was found.
This implementation efficiently finds and confirms the presence of a fixed point using binary search, making it optimal for sorted arrays, ensuring a time complexity of O(log n)
, where n
is the number of elements in the array.
class Solution {
public int searchFixedPoint(int[] data) {
int lo = 0, hi = data.length - 1;
int result = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (data[mid] == mid) {
result = mid;
hi = mid - 1; // Shift search area to left
} else if (data[mid] < mid) {
lo = mid + 1; // Search in right half
} else {
hi = mid - 1; // Search in left half
}
}
return result;
}
}
The provided Java code implements a method to find a fixed point in an array. A fixed point is an index where the element at that index is equal to the index itself, e.g., data[i] == i
.
The method named searchFixedPoint
employs a binary search algorithm to efficiently locate the fixed point. Here’s how it functions:
- Initialize two pointers,
lo
andhi
, representing the start and end of the array segment being searched. - Initiate a loop that continues as long as
lo
is less than or equal tohi
. - Calculate the midpoint of the current segment using
(lo + hi) / 2
. This position is continuously updated based on the results of each comparison. - If the element at this midpoint position equals the midpoint (i.e.,
data[mid] == mid
), then:- Assign this position as the result.
- Adjust
hi
to search the left side of the array for any earlier fixed point occurrence.
- If the element at the midpoint is less than the midpoint (
data[mid] < mid
), move thelo
pointer tomid + 1
to search the right half of the array segments. - If the element at the midpoint is greater than the midpoint, adjust the
hi
pointer tomid - 1
to search the left half.
The method returns the first occurrence of the fixed point if it exists, returning -1
if no fixed point is found. This return value effectively indicates that no index in the array satisfies the condition data[index] == index
.
This approach ensures a time complexity of O(log n)
due to the binary search technique, making it efficient for large datasets.
class Solution:
def findFixedPoint(self, values: List[int]) -> int:
start, end = 0, len(values) - 1
result = -1
while start <= end:
middle = (start + end) // 2
if values[middle] == middle:
result = middle
end = middle - 1
elif values[middle] < middle:
start = middle + 1
else:
end = middle - 1
return result
Discover the method to identify a fixed point in an array where the element's value equals its index, using Python. The provided code implements a binary search technique to efficiently locate such a position within a sorted list of integers.
- The function
findFixedPoint
initializes two pointers,start
andend
, to represent the range currently being searched. - A variable
result
is initialized to-1
, to store the result if a fixed point is found. - A while loop continues until
start
exceedsend
. Inside this loop:- Calculate the midpoint of the current range.
- If the element at the midpoint index is equal to the index itself, update
result
with this index and narrow the search to the left half to possibly find a lower fixed point. - If the element is less than the midpoint index, adjust the
start
pointer to focus on the right half; otherwise, adjust theend
pointer to focus on the left half.
- The process concludes by returning
result
, which will either be-1
(indicating no fixed point was found) or the index of a fixed point, with preference given to the lowest fixed point if multiple are present.
Implement this solution to determine the fixed point in your data, ensuring efficient performance even with sizable input arrays.
No comments yet.