Binary search first >= target
Hard
Java
Control Flow
26 views
Problem Statement
Task: return the first index where a[i] >= target in a sorted array, else return n.
Input Format
An integer n (size of sorted array)
Then n integers (sorted in non-decreasing order)
An integer target
Then n integers (sorted in non-decreasing order)
An integer target
Output Format
An integer: the first index i such that a[i] >= target
If no such index exists, return n.
If no such index exists, return n.
Example
5 1 3 5 7 9 6
3
Constraints
• n ≥ 0
• Array is sorted
• Use efficient search (binary search)
• Array is sorted
• Use efficient search (binary search)
Concept Explanation
We need the lower bound of target:
the first position where the value is not less than target.
the first position where the value is not less than target.
Step-by-Step Explanation
1.Read n, the sorted array, and target.
2.Set left = 0, right = n - 1, ans = n.
3.While left = target:
• Set ans = mid.
• Move right = mid - 1 (search left side).
• Else:
• Move left = mid + 1.
4.After loop ends, return ans.
2.Set left = 0, right = n - 1, ans = n.
3.While left = target:
• Set ans = mid.
• Move right = mid - 1 (search left side).
• Else:
• Move left = mid + 1.
4.After loop ends, return ans.
Concept Explanation
We need the lower bound of target:
the first position where the value is not less than target.
the first position where the value is not less than target.
Step-by-Step Explanation
1.Read n, the sorted array, and target.
2.Set left = 0, right = n - 1, ans = n.
3.While left = target:
• Set ans = mid.
• Move right = mid - 1 (search left side).
• Else:
• Move left = mid + 1.
4.After loop ends, return ans.
2.Set left = 0, right = n - 1, ans = n.
3.While left = target:
• Set ans = mid.
• Move right = mid - 1 (search left side).
• Else:
• Move left = mid + 1.
4.After loop ends, return ans.
Input / Output Format
Input Format
An integer n (size of sorted array)
Then n integers (sorted in non-decreasing order)
An integer target
Then n integers (sorted in non-decreasing order)
An integer target
Output Format
An integer: the first index i such that a[i] >= target
If no such index exists, return n.
If no such index exists, return n.
Constraints
• n ≥ 0
• Array is sorted
• Use efficient search (binary search)
• Array is sorted
• Use efficient search (binary search)
Examples
Input:
5
1 3 5 7 9
6
Output:
3
Example Solution (Public)
static int lowerBound(int[] a,int target){int l=0,r=a.length;while(l<r){int m=l+(r-l)/2; if(a[m]>=target) r=m; else l=m+1;}return l;}
Official Solution Code
static int lowerBound(int[] a,int target){int l=0,r=a.length;while(l<r){int m=l+(r-l)/2; if(a[m]>=target) r=m; else l=m+1;}return l;}
Please login to submit solutions.