#include <vector> #include <iostream> using namespace std; int floornum(vector<int> arr, int N, int k) { int start =0, end = N-1, index = -1; int mid; while (start <= end) { mid = (start+end)/2; if(arr[mid]==k) return mid; else if(arr[mid]>k && arr[mid-1]<=k) return (mid-1); else if(arr[mid]>k && arr[mid-1]>k) end = mid-1; else if(arr[mid]<k) start = mid+1; } if(start == N) index = N-1; return index; } int main() { //code int t; cin>>t; while(t--) { int N, k; cin>>N>>k; vector<int> arr; for(int i=0; i<N; ++i) { int temp; cin>> temp; arr.push_back(temp); } cout <<floornum(arr,N,k)<<endl; } return 0; }
Problem Description
Given a sorted array, arr[] and a value, x, find floor of x in given array. Floor of x is the largest element in arr[] such that the element is smaller than or equal to x. If floor exists, then return index of it, else return -1
-
Test Case 1
Input (stdin)
3 7 1 1 2 8 10 11 12 19 7 5 1 2 8 10 11 12 19 7 10 1 2 8 10 11 12 19
Expected Output
0 1 3
-
Test Case 2
Input (stdin)
2 6 1 1 8 10 11 12 19 6 5 1 2 8 10 12 19
Expected Output
0 1