Implement Lower Bound

Slug: implement-lower-bound

Difficulty: Easy

Id: 878537

Topic Tags: Binary Search, Arrays, Algorithms

Company Tags: None

Summary

Given an array and a target value, find the lower bound of the target value in the sorted array. The lower bound is the smallest index i such that the element at index i is greater than or equal to the target value.

This problem involves binary search and manipulation of arrays.

Detailed Explanation

To solve this problem, we can use binary search to find the lower bound of the target value. We start by considering the middle element of the array. If the middle element is less than the target value, we know that all elements to the left of the middle element are also less than the target value. Therefore, we can discard the left half of the array and repeat the process with the right half. This process continues until we find the lower bound.

Here's a step-by-step breakdown of the solution:

1. Initialize two pointers, left and right, to the start and end of the array respectively.
2. While left is less than or equal to right, calculate the middle index mid.
3. If the element at index mid is less than the target value, update left to mid + 1.
4. Otherwise, update right to mid - 1.
5. Repeat steps 2-4 until left is greater than or equal to right.
6. The lower bound is the index left.

Time complexity: O(log n), where n is the length of the array.

Space complexity: O(1).

Here's a simple ASCII art diagram illustrating the binary search process:

  +---------------+
  |       left    |
  +---------------+
  |   middle     |
  +---------------+
  |      right   |
  +---------------+

  -> move left pointer to mid + 1
  (if element at mid is less than target)
  <- move right pointer to mid - 1

Optimized Solutions

Java