10 Find Floor of an element in a Sorted Array
Vložit
- čas přidán 16. 03. 2020
- FIND FLOOR OF AN ELEMENT IN A SORTED ARRAY:
Given a sorted array and a value x, the floor of x is the largest element in array smaller than or equal to x. Write efficient functions to find floor of x.
Example:
Input : arr[] = {1, 2, 8, 10, 10, 12, 19}, x = 5
Output : 2
2 is the largest element in arr[] smaller than 5.
PROBLEM STATEMENT LINK:https:www.geeksforgeeks.org/floor-i...
PLAYLIST LINK: • Binary Search | Interv... .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.
best series on binary search
surely is..
Legend , using exactly same template with minor changes for almost every problem. Respect++
just wanted to say, you're doing a great service to the society! :)
Think about approach given below it may help:
floor : end pointer after the whole execution of loop,if mid is not exist.
ceil : start pointer after the whole execution of loop,if mid is not exist.
same i was thinking if target == arr[mid] return mid else left
Yaa we should return start if elementnis not available 😅
Thanks a lot boss for such amazing content
the first question I was able to do on my own on the bases of previoous questions Thanks biro...
Approach
The problem is little bit modified when compared to finding the floor/ceil of an element using binary search. Usually to find the floor,(Here I am assuming you know the basic binary search concept of finding the floor and ceil) we consider the rightmost search space.
if(nums[mid]
There's another way to do this, an element would be the floor of K if that element is less than K and the element next to is greater than 4 or is the end of the array.
Here is the code would look like
int solve(long long int arr[], int i, int j, int k, int N) {
if (i>j)
return -1;
int mid = (i + j)/2;
if (arr[mid]==k)
return mid;
if (arr[mid] < k && (arr[mid+1] > k || mid+1==N))
return mid;
if (kj)
return -1;
int mid = (i + j)/2;
if (arr[mid] k || mid+1==N))
return mid;
if (k
good teaching style,able to solve by myself
Here's my simple Soln:
int findFloor(vector a, long long n, long long x){
int l = 0;
int h = n-1;
while(l
This problem is similar as insert and search
Will lower bound work here if I need index instead of element?
Another good idea maybe is to find the index of first greater element than x(using binary search) and then index-1 will be the answer.
int findFloor(vector v, long long n, long long x){
// Your code here
int start=0;
int end=n-1;
int floor=-1;
while(start
@@imshivendra
1. We have to return index not the element so change v[mid] to mid under the if condition
2. floor is a C++ keyword so change it to Floor or something else
u can use uprBOND and lwrbnd FUNCTION
@@chetanraghavv int start=0,mid,res=-1,end=n-1;
while(startv[mid])
{
res=mid;
start=mid+1;
}
else
end=mid-1;
}
return res;
such a helpful series...thanks a lot😇
int findFloor(vector v, long long n, long long x){
// Your code here
int start=0;
int end=n-1;
int floor=-1;
while(start
@@imshivendra we need to return INDEX and you are returning the ELEMENT
@@imshivendra bro else se to terminate kro kamsekum
Bhaiya please upload more videos.The way you teach is incredible 👌.I loved watching your video ❤️✨. Please bhaiya upload more video🙏🙏.
int findFloor(vector v, long long n, long long x){
// Your code here
int start=0;
int end=n-1;
int floor=-1;
while(start
Sir paper prr jo video aap banate ho... Vo bahut sahi hai... Please paper prr banao....
Aur aapke video sach me bahut jayda helpful hai.....
Thankyou for making such an awesome videos for us!
I always confused between ceil and floor concept thank you for connecting it with the room concept...
int findFloor(vector v, long long n, long long x){
// Your code here
int start=0;
int end=n-1;
int floor=-1;
while(start
we can just return hi or end when lo == hi or start == end in normal binary search, and hi+1 for ceil.
Nice vedio Sir. Sir please upload backtracking questions vedio as well
Will upload more video in the month of may !! Till then keep on sharing and help this channel grow + that keeps me motivated to make more videos !! ✌️❤️
@@TheAdityaVerma please make a playlist of graph also....sir❤❤❤❤❤
I think its better to use upper and lower bound for floor and ceil respectively.
its an implementation q right??
My Observation ,
Because the array is sorted so
if(mid>5) then the mid-1 should be less than 5 then return mid -1 else continue loop e=mid-1;
if(a[mid]>5){
if(a[mid-1]
But can someone tell me the reason why it's not working whenever I'm trying to take the user input for cin>>arr[i]..?
floor and ceil of an soted array solution.
public class Main
{
public static void main(String[] args) {
int arr[] = {6,7,8,9,10};
int key = 5;
int c=ceil(arr,key);
int f =floor(arr,key);
System.out.println("ceil is "+c);
System.out.println("floor is "+f);
}
private static int ceil(int arr[], int key)
{
int lo = 0;
int hi = arr.length-1;
int ans = -1;
while(lokey)
{
ans = arr[mid];
hi = mid - 1;
}
if(arr[mid] < key)
{
lo = mid + 1;
}
}
return ans;
}
private static int floor(int arr[], int key)
{
int lo = 0;
int hi = arr.length-1;
int ans =-1;
while(lo
great
baki kai sorting method kaha pe use honge to??
I think We can simply run Binary Search and after the while loop we'll get end pointing the floor and start pointing the ceil, Assuming target isn't present and the loop runs until start doesn't become larger than end.
int ans(-1);
if (key < arr[0]) //If our key is less than the smallest element in the array
ans = -1;
else if (key > arr[n - 1]) //If our key is greater than the largest element in the array
ans = arr[n - 1];
else
{ //Simple binary search just take care of the condition
int low(0), high(n - 1);
while (low
BESTTTT !!!!!!!!
JAVA SOLUTION:-
public static int FloorOfNumber(int[] arr,int key) {
int n = arr.length;
int start = 0, end = n - 1;
int max=0;
while(startkey)
{
end=mid-1;
}
if(arr[mid]
similar to finding first index of element 👍👍👍👍
Here is a recursive CPP implementation of the approach shown in this video
int solve(long long int arr[], int i, int j, int k, int candidate) {
if (i>j)
return candidate;
int mid = (i + j)/2;
int c = candidate;
if (arr[mid]arr[candidate])
c = mid;
}
if (k
int findFloor(vector v, long long n, long long x){
// Your code here
int start=0;
int end=n-1;
int floor=-1;
while(start
@@imshivendra same problem bro, 2nd test case failing (input too large)
simple solution in python
#floor of the element in sorted array
class Solution:
def bs(self,nums,target):
l=0
r=len(nums)-1
res=0
for i in range(len(nums)):
mid=l+(r-l)//2
if nums[mid]target:
r=mid-1
print(res)
t1=Solution()
t1.bs([11,12,15,18,2,5,6,8],16)
In Simple way we have to return upper_bound( x ) -1;
class Solution{
static int findFloor(long arr[], int n, long x)
{
return upper_bound(arr,x) - 1;
}
static int upper_bound(long[] arr,long x){
int low = 0, high = arr.length;
while(low
Hi Aditya..I tried the solution on leet code
public class Solution {
public int SearchInsert(int[] nums, int target) {
int start=0,end=nums.Length-1,mid;
int result=-1;
while(start
give the link of leetcode problem . I don't fiond this question on leetcode
For those who are considering this logic is a little bit complex, actually it's not and its more logical and impressive to the interviewer(because you can actually explain how you're finding the floor value), rather than just performing binary search and returning mid or high index, coz fortunately it's giving the answer.
I've tried briefing down this concept in five steps:-
1) Declare a res variable, initialize it with -1, in case no smaller value is found in the whole array, then this -1 will be returned.
2) Start with finding the middle element. Compare the middle element with target value.
3) If middle is equal to the target, you don't have to do anything, just store the res=mid, and break, come out of the loop.
4) If middle element is less than the target element, then this middle element can be the possible answer for the floor , so just store this middle into res. But as the definition of floor function says that apart from being smaller than the target element , it should also be the greatest among candidate answers. Since, we've found an element which is smaller than the target, we cannot stop here, we need to check whether there's an element which is greater than this middle, but still smaller than the target. So, whenever we want to move to the greater side, we always move towards right.
so do, first=mid+1, if any greater element is found than this middle, then we'll store that in res, otherwise, we've saved our previous answer in the res variable.
5) If middle element is greater than the target, then you know for sure that this middle cannot be a candidate for floor value, and you'll not store this into res. You'll move towards smaller values, that is towards left, that is last=mid-1. And keep on searching greatest smaller value for the target in the left part only.
Here's the snippet:-
int findFloor(vector v, long long n, long long x){
int res=-1;
if(n==1 && v[0]x)
return -1;
else
{
int first=0,last=n-1,mid;
while(first
if(v[mid]==x)return mid;
we can directly return mid nah
@@spoidermon4323 No, we cannot just return it, and then come out of the loop. I've explained in point no. 4 and 5, that why we've to traverse the either part of the array, even we've found one of the candidate element.
Thank you for the English explanation
Aditya Bhaiya Your intuition is not working here. aapka logic gfg pe multiple test cases me fail ho raha hai
int findFloor(vector v, long long n, long long x){
// Your code here
int start=0;
int end=n-1;
int floor=-1;
while(start
Can we not do normal BS iteration and then return the value at "end" index (i.e when x is not the floor) ?
yes you can
what if there are duplicate elements, then which index should be return.
ex- 2,4,5,6,10,10,10,10,10,10,10
for finding floor of 10 ...should it be 5 or 4?
5
are bhai khaha gayab ha tu , or videos dal de yr , bohot help hori ha ekdum bhai
Returning mid if element is present otherwise returning mid Or mid - 1 instead of -1 after the while loop in the binary search approach will do the same work.
Yes bro you are right , i solved it at gfg.... and one more thing that should be checked very first, if(a[n-1])>=key) so return n-1 or a[n-1].
@@AJ-gg1jc I think this case will be automatically handled no need for checking.
@@anuragshah516 yeah but i got something wrong then i checked my code and updated that.....
I was juat testing on custome input..... it is possible that , code was right
Bhai kya apni approach explain kar sakte ho ?
Mujhe samajh nhi aaya
@@gurnoorsingh2954 Bro just do one thing with simple binary search code..... print its mid after each iteration, you will find that the last mid you printed out, is your answer here if the element is present otherwise "mid-1" is your answer.... Now you may ask that why are we checking mid-1 , because a[mid] can be larger than the given key element.... so as we know a[mid-1] will always be smaller or floor. ...... see my code here...>>>>
Accepted on gfg,....... function which return floor(given key element)...
#include
using namespace std;
int flor(int a[],int n,int key){
if(a[n-1]
best
function floor_in_sorted_array(arr, ele){
let start = 0;
let end = arr.length -1;
let res =-1;
while(start= ele){
end = mid -1
}
else if(arr[mid]
//floor of an elelment in sorted array
int Floor_inSorted(int a[] , int key , int n)
{
int l = 0;
int h = n-1;
int mid;
int result;
while(l
Practice link?
Check Description
JAVA Solution
// Function to find floor of x
// arr: input array
// n is the size of array
static int findFloor(long arr[], int n, long x)
{
int res = -1;
int l = 0;
int r = n-1;
while(l
Yaa we should return start if elementnis not available 😅😅
This became a little complex. Rather than this we could have simply used binary search to search for the element. If the element would have been present then the binary search would have simply returned the index of that element. Otherwise at the end of the loop in the binary search instead of returning -1 at the end we will compare the element at the start index and the element at the end index and return whichever is the smaller of them.
yeah, you're right, we can make this more simple, just keep on iterating through the while loop, when the control will come out of the loop, just check that ar[mid]
how to write code please
int findFloor(vector v, long long n, long long x){
// Your code here
int start=0;
int end=n-1;
int floor=-1;
while(start
in gfg the question is asking to find index of floor you are returning the element, return mid instead of v[mid]
end always give you floor value index if element is not present
Geart logic keep it up !
int findFloor(long long int arr[], int N, long long int K) {
long long int low=0;
long long int high = N-1;
int res=-1;
while(lowK)
{
high = mid-1;
}
else if(arr[mid]
Use simple Binary Search, and outside while instead of returning -1, return low;
Nice solution, did your husband give it to you?
@@boredpotato6366 gonna cry?
your code is not working for multiple test cases
@@imshivendra I've literally submitted my code on leetcode
@@gigachad6844 Actuall I didn't find this problem n leetcode if you have problem link can you plese give it to me
Intuitive solution :
class Solution{
// Function to find floor of x
// arr: input array
// n is the size of array
static int findFloor(long arr[], int n, long x)
{
int start=0,end=n-1;
while(start
Hey could you please explain why are you returning the end?
Loop not stopping......
int l=0;
int r=nums.length-1;
while(l=key)
r=m-1;
else
l=m+1;
}
return l;
#include
using namespace std;
int main()
{
int n,ele;
cin>>n;int a[n];
for(int i=0;i>a[i];
coutele;
int start =0,end=n-1,res;
while(start
#include
using namespace std;
int binarySearch(int arr[], int n, int key)
{
int res;
int l=0;
int r=n-1;
while(l key)
{
r=mid-1;
}
else if(key>arr[mid])
{
l=mid+1;
res= arr[mid];
}
}
// We reach here when element is not present in array
return res;
}
// Driver Code
int main()
{
int arr[] = {-3, 2, 10, 39, 45};
int n = sizeof(arr) / sizeof(arr[0]);
int key=40;
cout
int start=0,mid,res=-1,end=n-1;
while(startv[mid])
{
res=mid;
start=mid+1;
}
else
end=mid-1;
}
return res;
this was my solution will it work??
int floor(int a[],int n,int t){
int l=0,h=n-1;
while(lt){
h=mid-1;
}else{
l=mid+1;
}
}
return -1;
}
int binarySearch1(int arr[],int len,int target){
int start = 0;
int end = len-1;
while(start target) end = mid -1;
else start = mid + 1;
}
return end;
}
// Online C++ compiler to run C++ program online
#include
#include
using namespace std;
int floor(vector &arr, int k)
{
int start=0, end=arr.size()-1,mid;
while(start
//c++ code:
int findFloor(vector v, long long n, long long x){
// Your code here
long long start=0;
long long end=n-1;
long long mid;
long long index=-1;;
while(start
int findFloor(vector v, long long n, long long x){
// Your code here
int s=0;
int e=n-1;
int res = -1;
while(s
Python Solution:-
class Solution:
#User function Template for python3
#Complete this function
def findFloor(self,A,N,X):
#Your code here
result = -1
start = 0
end = N-1
while start
Simple and easy understandable code
#include
using namespace std;
int main(){
int arr[]={1,2,3,4,8,10,12,19};
int n=sizeof(arr)/sizeof(arr[0]);
int target=11;
int s,e,m;
s=0;
e=n-1;
while(s
Please bhaiya videos banate raho please 🙏
CODE
#include
using namespace std;
/*
Floor in the sense - if we are searching the floor of 5 and that value is present in array then return that value. Otherwise return key-1 value;
*/
void print_arr(int arr[], int size);
int find_floor(int arr[], int size, int key);
int main(){
int size, key; cin>>key>>size;
int arr[size];
for(int i = 0; i < size; i++){
cin>>arr[i];
}
print_arr(arr, size);
int res = find_floor(arr, size, key);
if(res
// C++ Solution With Binary Search →
int Floor(int arr[], int size, int key){
int start = 0;
int end = size-1;
int mid= start + (end - start / 2);
int ans=0;
while(start arr[mid]){
ans = arr[mid];
start = mid + 1;
}else if( key < arr[mid]){
end = mid - 1;
}
mid = start + (end - start / 2);
}
return ans;
}
int findFloor(vector v, long long n, long long x){
// Your code here
int start=0;
int end=n-1;
int floor=-1;
while(start
Bhai maine bhi yahi cde likha hai lekin ye code kaam nahi kar raha hai GFG par. you can see my code
@@imshivendra
try this one
int findFloor(vector v, long long n, long long x){
using ll=long long;
ll start = 0;
ll end = n-1;
ll mid = start + (end - start/2);
ll ans = -1;
while(start v[mid]){
ans = mid;
start = mid + 1;
}else if(x < v[mid]){
end = mid - 1;
}
mid = start + (end - start/2);
}
return ans;
}
Thanks brother I got solution
try writing code in a compiler :)
💬💬💬💬💬💬
full code:
public static int findFloorOfElement(int[] arr, int k) {
int start = 0;
int end = arr.length - 1;
while (start
static int findFloor(long arr[], int n, long x)
{
int s=0;
int e=n-1;
int min=-1;
while(s
Same
Please explain in English
int floor(int a[],int target,int n)
{
int low=0,high=n-1,res=-1;
while(lown>>key;
int a[n];
for(int i=0;i>a[i];
}
int ans=floor(a,key,n);
cout
public class FindFloorElementSortedArray {
public static void main(String[] args) {
int arr[] = { 1, 2, 3, 4, 8, 9, 10, 11, 12 };
int k = 5;
System.out.println(solve(arr, k));
}
static int solve(int arr[], int k) {
int left = 0;
int right = arr.length - 1;
int ans = -1;
while (left k) {
right = mid - 1;
} else {
ans = arr[mid];
left = mid + 1;
}
}
return ans;
}
}