Code Logo

Find First Greater Element

Published at05 Jan 2026
Created by
Medium 23 views
Like13

Given a sorted array of integers and a target value, return the index of the first element that is strictly greater than the target. If no element in the array exceeds the target, return -1.

The answer is an index, not the value itself. Values that are exactly equal to the target do not count — the search must skip past them and find the first value that is genuinely larger.

For example, in [1,2,2,3] with target 2, the answer is 3 because the first value bigger than 2 is 3 at index 3 (the two copies of 2 at indices 1 and 2 are skipped). In [2,4,6,8] with target 8, the answer is -1 because no value is greater than 8. In [1,3,5,7,9] with target 4, the answer is 2 because 5 is the first value above 4.

This is known as an upper-bound search. It is the mirror image of the lower-bound search and is used in interval queries, bisection methods, and problems that need to find the insertion point just past a value. Together with lower-bound search, it enables finding ranges of equal values in sorted data.

Edge cases include an empty array (return -1), a target smaller than every element (return 0, since even the first element is greater), a target larger than every element (return -1), and a target whose value appears many times (the answer is the index just past the last copy).

Example Input & Output

Example 1
Input
nums = [2, 4, 6, 8], target = 8
Output
-1
Explanation

No element is greater than 8.

Example 2
Input
nums = [1, 2, 2, 3], target = 2
Output
3
Explanation

The first element greater than 2 is 3, at index 3.

Example 3
Input
nums = [1, 3, 5, 7, 9], target = 4
Output
2
Explanation

The first element greater than 4 is 5, at index 2.

Algorithm Flow

Recommendation Algorithm Flow for Find First Greater Element

Solution Approach

Use binary search to find the first position where nums[i] > target. When the middle value is already greater than the target, record it as a candidate and search the left half for an earlier one. When the middle value is at most the target, search the right half.

function find_first_greater_element(nums, target) {
  var left = 0, right = nums.length - 1, ans = -1;
  while (left <= right) {
    var mid = Math.floor((left + right) / 2);
    if (nums[mid] > target) { ans = mid; right = mid - 1; }
    else left = mid + 1;
  }
  return ans;
}

The ans variable holds the leftmost index found so far where the value exceeds the target. Each time a qualifying value is found, the search window shifts left to look for an even earlier occurrence. If no value ever qualifies, ans stays -1.

Time complexity is O(log n), space complexity is O(1).

Best Answers

java
class Solution {
    public int find_first_greater_element(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        int ans = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] > target) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }
}