1. Implement Lower Bound.md

Difficulty	Source	Tags
Easy	160 Days of Problem Solving (BONUS PROBLEMS 🎁)	Binary SearchArrays

🚀 1. Implement Lower Bound 🧠

The problem can be found at the following link: Problem Link

💡 Problem Description

Given a sorted array arr[] and a number target, the task is to find the lower bound of the target in the given array. The lower bound of a number is defined as the smallest index in the sorted array where the element is greater than or equal to the given number.

Note: If all the elements in the array are smaller than the target, the lower bound will be the length of the array.

🔍 Example Walkthrough

Input:

arr[] = [2, 3, 7, 10, 11, 11, 25], target = 9

Output:

3

Explanation:
3 is the smallest index where the element arr[3] = 10 is greater than or equal to 9.

Input:

arr[] = [2, 3, 7, 10, 11, 11, 25], target = 11

Output:

4

Explanation:
4 is the smallest index where the element arr[4] = 11 is greater than or equal to 11.

Input:

arr[] = [2, 3, 7, 10, 11, 11, 25], target = 100

Output:

7

Explanation:
Since no element is greater than 100, the lower bound will be the length of the array, which is 7.

🎯 My Approach

We can solve this problem using Binary Search because the array is sorted. The key idea is to narrow down the search space and find the smallest index at which the target can be inserted to maintain the sorted order.

Step-by-Step:

1. Initialize Variables:
   We maintain two pointers, lo and hi, initialized to 0 and the length of the array, respectively.

2. Binary Search Loop:
   While lo < hi:

   • Calculate the middle index mid.
   • If arr[mid] is less than the target, we know the target must be to the right of mid, so set lo = mid + 1.
   • Otherwise, set hi = mid. This is because the target might be at mid or to the left of it, so we shrink the search space accordingly.

3. Return the Result:
   After the loop ends, lo will be the smallest index where the element is greater than or equal to the target.

🕒 Time and Auxiliary Space Complexity

• Time Complexity:
  The algorithm performs a binary search, so the time complexity is O(log n), where n is the size of the array. In each iteration, the search space is halved.

• Auxiliary Space Complexity:
  The space complexity is O(1) since we are only using a constant amount of space (pointers lo, hi, and mid).

📝 Solution Code

Code (C++)

class Solution {
  public:
    int lowerBound(vector<int>& arr, int target) {
        int lo = 0, hi = arr.size();
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] < target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
};

Code (Java)

class Solution {
    int lowerBound(int[] arr, int target) {
        int lo = 0, hi = arr.length;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
}

Code (Python)

class Solution:
    def lowerBound(self, arr, target):
        lo, hi = 0, len(arr)
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if arr[mid] < target:
                lo = mid + 1
            else:
                hi = mid
        return lo

📢 Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count