easyBinary SearchPattern: Binary Search
Find First Greater Element Index Solution
Problem Statement
Given a sorted array of distinct integers `values` and a target integer `target`, find the index of the first element in `values` that is strictly greater than `target`. If no such element exists, return -1.
Examples
Example 1:
Input:{"values":[2,5,8,12,16,23,38,56,72,91],"target":15}
Output:4
Explanation: Find the index of the first element strictly greater than 15. The elements greater than 15 are 16, 23, 38, 56, 72, 91. The first of these is 16, which is at index 4.
Example 2:
Input:{"values":[10,20,30,40,50],"target":50}
Output:-1
Explanation: Find the index of the first element strictly greater than 50. There is no element in the array strictly greater than 50. Thus, the output is -1.
Example 3:
Input:{"values":[5,10,15,20],"target":3}
Output:0
Explanation: Find the index of the first element strictly greater than 3. The first element, 5, is greater than 3. Thus, the index is 0.
Constraints
- 1 <= values.length <= 10^5
- 1 <= values[i] <= 10^9
- values is sorted in strictly increasing order.
- -10^9 <= target <= 10^9
Time: O(log n) Space: O(1)
Use binary search. In each step, compare the middle element with the `target`. If the middle element is greater than `target`, it might be the first such element, so record its index and try searching in the left half. Otherwise, search in the right half. The search continues until the search space is exhausted, returning the smallest index found that satisfies the condition, or -1 if none was found.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def find_first_greater_element_index(values, target):
low = 0
high = len(values) - 1
ans = -1
while low <= high:
mid = low + (high - low) // 2
if values[mid] > target:
ans = mid # Potential answer, try to find an earlier one
high = mid - 1
else:
low = mid + 1 # Middle element is too small or equal, search in the right half
return ans