public class Solution {
public static int lowerBound(int []arr, int n, int x) {
for(int i=0;i<arr.length;i++){
if(arr[i]>=x){
return i;
}
if(arr[n-1]<x){
break;
}
}
return n;
}
}
Problem
Submissions
Hints & solutions
Discuss
Implement Lower Bound
Easy
0/40
Average time to solve is 20m
Contributed by
311 upvotes
Problem statement
You are given an array 'arr' sorted in non-decreasing order and a number 'x'. You must return the index of the lower bound of 'x'.
1. For a sorted array 'arr', 'lower_bound' of a number 'x' is defined as the smallest index 'idx' such that the value 'arr[idx]' is not less than 'x'.If all numbers are smaller than 'x', then 'n' should be the 'lower_bound' of 'x', where 'n' is the size of array.
2. Try to do this in O(log(n)).
Input: ‘arr’ = [1, 2, 2, 3] and 'x' = 0
Output: 0
Explanation: Index '0' is the smallest index such that 'arr[0]' is not less than 'x'.
Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The first line of contains an integer ‘n’, the number of elements in the array 'arr'.
The second line contains 'n' single space-separated integers representing the elements in the array 'arrr'.
The third line contains an integer ‘x’, the number whose lower bound is to be found.
Return the lower bound.
Constraints:
1 <= ‘n’ <= 10^5
0 <= ‘arr[i]’ <= 10^5
1 <= ‘x’ <= 10^5
Sample Input 1:
6
1 2 2 3 3 5
0
Sample Output 1:
0
Explanation Of Sample Input 1 :
Index '0' is the smallest index such that 'arr[0]' is not less than 'x'.
Sample Input 2:
6
1 2 2 3 3 5
2
Sample Output 2:
1
Sample Input 3:
6
1 2 2 3 3 5
7
Sample Output 3:
6
Hint
Hint 1
This problem can be solved using binary search.
Approaches (1)
Approach 1
Binary Search
Let's define the states using ‘l’ and ‘r’ as:
- The elements having index less than ‘l’ are smaller than ‘x’.
- The elements from index ‘l’ to ‘r’ - 1 are unchecked.
- The elements having index greater than or equal to ‘r’ are greater than equal to ‘x’.
The conditions on ‘m’:
- If the element at position ‘m’ is less than ‘x’, this means ‘m’ should be in case 1. Therefore we are assigning ‘m’ to ‘l’ - 1. This means ‘l’ should be equal to ‘m’ + 1.
- If the element at position ‘m’ is greater than or equal to ‘x’, this means ‘m’ should be in case 3. Therefore we are assigning ‘m’ to ‘r’.
When will this loop end?
The loop should end when there is no element in case 2. This means the loop will work while ‘l’ <= ‘r’ - 1, or we can write ‘l’ < ‘r’.
The steps are as follows:
int lowerBound(int ‘arr[]’, int ‘n’, int ‘x’)
- Let ‘l’ = 0, ‘r’ = ‘n’, ‘m’ = 0;
- While ‘l’ < ‘r’:
- ‘m’ = (‘l’ + ‘r’) / 2
- If ‘arr[m]’ < ‘X’:
- ‘l’ = ‘m’ + 1
- Else:
- ‘r’ = ‘m’;
- Return ‘r’.
Time Complexity
O(log ‘n’), where ‘n’ is the size of the array.
The array is split in half at each function call, and we deal with only one half.
Let the total number of function calls be ‘k’. Then approximately:
‘n’ / 2‘k’ = 1
‘n’ = 2‘k’
‘k’ = log2(‘n’)
Hence the time complexity is O(log ‘n’).
Space Complexity
O(1)
We are using only three variables, ‘l’, ‘r’ and ‘m’.
Hence the time complexity is O(1).
Code Solution
(100% EXP penalty)
Implement Lower Bound
All tags
Sort by
Interview problems
EASY APPROACH ✅✅✅✅ ||Finding Lower bound||java
26 views
0 replies
0 upvotes
Interview problems
VERY EASY CODE ✅ || BEATS 93 % || O(log n) 🔥
int lowerBound(vector<int> arr, int n, int x) {
// Write your code here
int ans = n;
int low = 0;
int high = arr.size()-1;
while(low<=high){
int mid = (low+high)/2;
if(arr[mid] >= x){
ans = mid;
high = mid-1;
}
else {
low = mid+1;
}
}
return ans;
}
54 views
0 replies
0 upvotes
Interview problems
2 lines code of C++
int lowerBound(vector<int> arr, int n, int x) {
// Write your code here
int lb=lower_bound(arr.begin(),arr.end(),x)-arr.begin();
return lb;
} 15 views
0 replies
1 upvote
Interview problems
Simple 🧠|| O(logn) || java || 100% easy
public class Solution {
public static int lowerBound(int []arr, int n, int x) {
// Write your code here
int ans=x;
int left=0;
int right=n-1;
while(left<=right)
{
int mid=(left+right)/2;
if(arr[mid]>=x)
{
ans=mid;
right=mid-1;
}
else{
left=mid+1;
}
}
return ans;
}
} 18 views
0 replies
0 upvotes
Interview problems
Simple 🧠|| java || easy💯 || Lower Bound
public class Solution {
public static int lowerBound(int []arr, int n, int x) {
// Write your code here
int min=x;
for(int j=n-1;j>=0;j--)
{
if(arr[j]>=x)
{
min=Math.min(j, min);
}
}
return min;
}
} 6 views
0 replies
0 upvotes
Interview problems
Simple Java solution
public static int lowerBound(int []arr, int n, int x) {
int low=0;
int high=n-1;
int ans = n;
while(low<=high){
int mid=(low+high)/2;
if(arr[mid]>=x){
ans=mid;
high=mid-1;
}else{
low=mid+1;
}
}
return ans;
} 32 views
0 replies
0 upvotes
Interview problems
answer without using ans variable ans with low,mi and high variables alone
int lowerBound(vector<int> arr, int n, int x) {
int low = 0;
int high = n-1;
while(low<=high) {
int mid = (low+high)/2;
if(arr[mid]>=x) high = mid-1;
else low = mid+1;
}
return low;
}
//Time complexity o(log2 n) log base2 n
48 views
0 replies
0 upvotes
Interview problems
easy solution for beginners
int lowerBound(vector<int> arr, int n, int x) {
// Write your code here
int low=0,high=n-1,ans=n;
while(low<=high)
{
int mid = (low+high)/2;
if(arr[mid] >= x)
{
ans=mid;
high=mid-1;
}
else
low = mid+1;
}
return ans;
}
24 views
0 replies
0 upvotes
Interview problems
Using C++ STL
#include<bits/stdc++.h>
int lowerBound(vector<int> arr, int n, int x) {
// Write your code here
int lb = lower_bound(arr.begin(),arr.end(),x)-arr.begin();
return lb;
}
23 views
0 replies
0 upvotes
Interview problems
C++ Solution - Striver Binary Search
/*
We need to find an element such that it has the lowest index that satisfies the condition of
being equal to greater than the target element
index i where arr[i] >= x
since it is sorted we have a hint that we can use binary search here
so we just need to find the element that is arr[i] >= x
but the only condition is that the index should be the smallest
*/
int lowerBound(vector<int> arr, int n, int x) {
// Write your code here
int start = 0;
int end = n-1;
int ans = n;
while(start <= end) {
int mid = start + (end - start)/2;
if(arr[mid] >= x) {
ans = mid; // this probably could be an answer
end = mid - 1;
}
else {
// now since the arr[mid] element is smaller that x, we need to search in the right side
start = mid + 1;
}
}
return ans;
}
41 views
0 replies
0 upvotes
1
2
3
4
C++ (g++ 5.4)
Console