https://algo.monster/problems/binary_search_first_element_not_smaller_than_target
“Bug” on c# template:
This will throw error if input ends with space(s)
List arr = SplitWords(Console.ReadLine()).Select(long.Parse).ToList();
I have to trim the string to make it work. i.e. List arr = SplitWords(Console.ReadLine().Trim()).Select(long.Parse).ToList();
Should instead greater than to greater or equal the target. I found a lot of questions missing the range of input data, it means sometime we had to deal with edge case (like 0, null, …). The description of question is ambiguous, too.
def first_not_smaller(arr: List[int], target: int) → int:
# WRITE YOUR BRILLIANT CODE HERE
for i in range(len(arr)):
if arr[i] >= target:
return i
Please tell me why this solution is not better that the answer provided? Is it just so a binary search solution is illustrated?
Had some issues with test #3.
Problem states “find the index of the first element in the array that is larger than or equal to the target.”
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 10
My code returns 10, the test fails because it wants 9 but 9 is not the first number greater than or equal to the target.
Code:
def first_not_smaller(arr: List[int], target: int) → int:
if len(arr) <= 1:
return 0
left = 0
right = len(arr) -1
while left <= right:
mid = (left + right) //2
if arr[mid] == target:
return mid + 1
elif arr[mid] < target:
if arr[mid + 1] > target:
return mid + 1
else:
left += 1
elif arr[mid] > target:
if arr[mid - 1] < target:
return mid
else:
right -= 1
The problem statement is asking for the “index” of the first element in the array that is larger than or equal to the target. In test #3, the number 10 in the array is the first number greater than or equal to the target. So we return its index, 9.
Your solution fails test #3 because of the first condition statement if arr[mid] == target: return mid + 1. It should be if arr[mid] == target: return mid.
def first_not_smaller(arr: List[int], target: int) → int:
left = 0
right = len(arr) - 1
new_target = -1
while left <= right:
mid = (left + right) // 2
if arr[mid] >= target:
new_target = mid
if arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return new_target
We want to make sure we initialize boundary_index = len(arr) otherwise if we enter a target number larger than the max number in the list, it will return -1 instead of len(arr).
I believe that the run time for yours would be O(n) while using binary reduces the runtime to O(log(n)). This matters with larger sets of data as half of the data doesn’t need to be searched every time the loop is ran.
Please find attached the way to solve this problem recursively:
def first_not_smaller_rec(arr: List[int],left: int, right: int, target: int, location: int) → int:
if left > right:
return location
mid = (left + right) // 2
if arr[mid] >= target:
location = mid
return first_not_smaller_rec(arr, left, mid-1, target, location)
else:
return first_not_smaller_rec(arr, mid + 1, right, target, location)
def first_not_smaller(arr: List[int], target: int) → int:
return first_not_smaller_rec(arr, 0, len(arr) - 1, target, -1)
I’m really confused so explanations said about a filter turning it into true and false – similar to the other problem of finding the boundary but actual solution doesn’t incorporate filter.
And I am unsure why we subtract in the mid:
let mid = left + Math.trunc((right - left) / 2);
The ‘filter’ is the if condition arr[mid] >= target.
left + Math.trunc((right - left) / 2) is to avoid potential overflow when left and right are very large as mentioned in the binary search intro.
I know this is suppose to be an Binary Search practice, and it buillds up. But you could literally solve the this problem by
for(int i = 0; i <= arr.size(); i++){
if(target <= arr.get(i))
return i;
}
return 0;
You are right. But what if you have an array of [0, 1, 2, 2, 2, … another 10k numbers … 9, 10, 11] and your target is 10.
What would be your time complexity then?
In your example would be O(n). In this example is O(log(n)).
To reinforce the idea of applying “arr[i] < target”, this can be implemented as:
def first_not_smaller(arr: List[int], target: int) → int:
# WRITE YOUR BRILLIANT CODE HERE
left, right = 0, len(arr)-1
boundary_idx = -1
while left <= right:
mid = left + (right-left)//2
if arr[mid] < target: #if element at arr[mid]<target, don't search left of mid
left = mid+1
else: #if element at arr[mid]>=target, store mid and don't search right of mid
boundary_idx = mid
right = mid-1
return boundary_idx
Great point, we can always brute force something, but in coding challenges especially we want to hit it at its best runtime, i.e. O(log(n)) here
so, this is the correct solution?
l, r = 0, len(arr)
while l < r:
mid = (l + r) // 2
if arr[mid] == target:
return mid
if arr[mid] < target:
l = mid + 1
else:
r = mid
return r
My Java-code is the following, maybe a litter faster than the official instruction, hope guys give some tips…
public static int firstNotSmaller(List arr, int target) {
// WRITE YOUR BRILLIANT CODE HERE
int left = 0;
int right = arr.size();
int mid = 0;
while (left <= right) {
mid = left + (right - left) / 2;
if (arr.get(mid) >= target) {
if (mid > 0 && arr.get(mid - 1) < target) {
return mid;
} else {
right = mid - 1 ;
}
} else if (arr.get(mid) < target) {
if (arr.get(mid + 1) >= target) {
return mid + 1;
} else {
left = mid + 1;
}
}
}
return mid;
}
No, arr[mid] could be a re-occurrence of the target value and we want the first repeating value. Eg. [1,3,4,5,5,5,5,5,5,5,7] and if my target is 5, arr[mid] would be 5 whereas the output should be index 3 i.e. the first occurrence of 5.
Is this solution good?
int first_not_smaller(std::vector arr, int target) {
// WRITE YOUR BRILLIANT CODE HERE
int l = 0;
int r = arr.size();
for (int i = l; i<=r;i++)
{
int mid = (l+(r-l) )/2;
if (arr[i] >= target)
return i;
else if(arr[i] == target)
r = mid -1;
else
l = mid +1;
}
return 0;
}