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

# 🚀 _1. Implement Lower Bound_ 🧠

The problem can be found at the following link: [Problem Link](https://www.geeksforgeeks.org/batch/gfg-160-problems/track/searching-bonus-problems/problem/implement-lower-bound)

## 💡 **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++)

```cpp
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)

```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)

```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](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Let’s make this learning journey more collaborative!

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

---

<div align="center">
  <h3><b>📍Visitor Count</b></h3>
</div>

<p align="center">
  <img src="https://visitor-badge.laobi.icu/badge?page_id=Hunterdii.GeeksforGeeks-POTD" />
</p>