Lower Bound in Sorted Array

Given a sorted array nums and a target value, return the index of the first element that is greater than or equal to the target. If no such element exists, return -1.

Difficulty:

JavaScript Solution

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

Explanation: Binary search keeps track of the first index where value is ≥ target.

⏱ O(log n) | 💾 O(1)

Java Solution

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

Explanation: When a valid element is found, search left to find the earliest index.

⏱ O(log n) | 💾 O(1)

Python Solution

def lower_bound(nums, target):
    left, right = 0, len(nums) - 1
    ans = -1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] >= target:
            ans = mid
            right = mid - 1
        else:
            left = mid + 1
    return ans

Explanation: Lower bound finds the first position where target can be inserted safely.

⏱ O(log n) | 💾 O(1)

Console

🎬 Share Your Coding Journey

Thumbnail Templates

Lower Bound in Sorted Array