Given a sorted array arr[] of size N without duplicates, and given a value x. Floor of x is defined as the largest element K in arr[] such that K is smaller than or equal to x. Find the index of K(0-based indexing).
Example 1:
Input:
N = 7, x = 0 
arr[] = {1,2,8,10,11,12,19}
Output: -1
Explanation: No element less 
than 0 is found. So output 
is "-1".
Example 2:
Input:
N = 7, x = 5 
arr[] = {1,2,8,10,11,12,19}
Output: 1
Explanation: Largest Number less than 5 is
2 (i.e K = 2), whose index is 1(0-based 
indexing).
Your Task:
The task is to complete the function findFloor() which returns an integer denoting the index value of K or return -1 if there isn't any such number.
Expected Time Complexity: O(log N).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ N ≤ 10^{7}
1 ≤ arr[i] ≤ 10^{18}
0 ≤ X ≤^{ }arr[n-1]

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Complete search

Starter code: class Solution:

    #User function Template for python3

    

    #Complete this function

    def findFloor(self,A,N,X):

        #Your code here

        

Solutions:
class Solution:

	def findFloor(self, A, N, X):
		ans = 0
		if X < A[0]:
			return -1
		low = 0
		high = N - 1
		while low <= high:
			mid = (low + high) // 2
			if A[mid] == X:
				return mid
			elif A[mid] > X:
				high = mid - 1
			else:
				low = mid + 1
				ans = mid
		return ans


from bisect import bisect_right

class Solution:

	def findFloor(self, arr, n, x):
		idx = bisect_right(arr, x)
		return idx - 1


class Solution:

	def findFloor(self, A, N, X):
		(l, r) = (0, N - 1)
		while l <= r:
			mid = (l + r) // 2
			if X < A[mid]:
				r = mid - 1
			elif X > A[mid]:
				l = mid + 1
			else:
				return mid
		return l - 1


class Solution:

	def findFloor(self, arr, n, x):
		l = 0
		r = len(arr) - 1
		floorindex = -1
		while l <= r:
			mid = (l + r) // 2
			if arr[mid] <= x:
				floorindex = mid
				l = mid + 1
			else:
				r = mid - 1
		return floorindex


class Solution:

	def findFloor(self, A, N, X):
		start = 0
		end = N - 1
		while start <= end:
			mid = (start + end) // 2
			if A[mid] <= X:
				if mid == N - 1 or A[mid + 1] > X:
					return mid
				else:
					start = mid + 1
			else:
				end = mid - 1
		return -1


class Solution:

	def findFloor(self, A, N, X):
		l = 0
		h = N - 1
		while l <= h:
			mid = (l + h) // 2
			if A[mid] <= X:
				if mid == N - 1 or A[mid + 1] > X:
					return mid
				else:
					l = mid + 1
			else:
				h = mid - 1
		return -1


class Solution:

	def findFloor(self, A, N, X):
		ans = -1
		l = 0
		h = N - 1
		while l <= h:
			mid = (l + h) // 2
			if A[mid] == X:
				ans = mid
				h = mid - 1
			elif A[mid] > X:
				h = mid - 1
			else:
				ans = max(ans, mid)
				l = mid + 1
		return ans


class Solution:

	def findFloor(self, arr, N, target):
		ans = -1
		(low, high) = (0, N - 1)
		while low <= high:
			mid = low + (high - low) // 2
			if arr[mid] == target:
				return mid
			elif arr[mid] > target:
				high = mid - 1
			else:
				ans = mid
				low = mid + 1
		return ans


class Solution:

	def findFloor(self, A, N, X):
		flag = 0
		if X in A:
			flag = 1
		A.append(X)
		A.sort()
		x = A.index(X)
		if x == 0:
			return -1
		if flag == 1:
			return x
		else:
			return x - 1


class Solution:

	def findFloor(self, A, N, X):
		left = 0
		right = N - 1
		res = -1
		while left <= right:
			mid = (left + right) // 2
			if A[mid] <= X:
				res = mid
				left = mid + 1
			else:
				right = mid - 1
		return res


class Solution:

	def findFloor(self, A, N, X):
		if N == 1:
			return 0
		start = 0
		end = N - 1
		res = -1
		while start <= end:
			mid = int(start + (end - start) // 2)
			if A[mid] == X:
				return mid
			elif A[mid] > X:
				end = mid - 1
			else:
				res = mid
				start = mid + 1
		return res


class Solution:

	def findFloor(self, A, N, X):
		N = len(A)
		for i in reversed(range(N)):
			if A[i] <= X:
				return i
		return -1


class Solution:

	def findFloor(self, A, N, X):
		count = -1
		for i in A:
			if i <= X:
				count = count + 1
			else:
				break
		if count == 0:
			return -1
		else:
			return count


class Solution:

	def findFloor(self, arr, N, k):
		low = 0
		high = N - 1
		while low <= high:
			mid = (low + high) // 2
			if arr[mid] <= k:
				if mid == N - 1 or arr[mid + 1] > k:
					return mid
				else:
					low = mid + 1
			else:
				high = mid - 1
		return -1


class Solution:

	def findFloor(self, A, N, X):
		if X >= A[N - 1]:
			return N - 1
		if X < A[0]:
			return -1
		for i in range(1, N):
			if A[i] > X:
				return i - 1
		return -1


class Solution:

	def findFloor(self, A, N, X):
		(max1, pos) = (-1, -1)
		for i in range(N):
			if A[i] <= X and max1 < A[i]:
				(max1, pos) = (A[i], i)
		return pos


class Solution:

	def findFloor(self, A, N, X):
		start = 0
		end = len(A) - 1
		ans = -1
		while start <= end:
			mid = (start + end) // 2
			if A[mid] == X:
				return mid
			elif A[mid] > X:
				end = mid - 1
			else:
				start = mid + 1
				ans = mid
		return ans


class Solution:

	def findFloor(self, arr, N, X):
		c = -1
		for i in range(N):
			if arr[i] <= X:
				c = i
			else:
				break
		return c


class Solution:

	def findFloor(self, A, N, X):
		lo = 0
		hi = N - 1
		ans = -1
		while lo <= hi:
			mid = (lo + hi) // 2
			if A[mid] < X:
				if ans == -1:
					ans = mid
				elif A[mid] > A[ans]:
					ans = mid
				lo = mid + 1
			elif A[mid] > X:
				hi = mid - 1
			else:
				return mid
		return ans


class Solution:

	def findFloor(self, A, N, X):
		left = 0
		right = N - 1
		fl = -float('inf')
		flindex = -1
		while left <= right:
			mid = (left + right) // 2
			if A[mid] == X:
				return mid
			if A[mid] > X:
				right = mid - 1
			if A[mid] < X:
				flindex = mid
				left = mid + 1
		return flindex


class Solution:

	def findFloor(self, a, n, x):
		l = 0
		h = len(a) - 1
		ans = -1
		while l <= h:
			mid = (l + h) // 2
			if a[mid] == x:
				return mid
			elif a[mid] > x:
				h = mid - 1
			else:
				l = mid + 1
				ans = mid
		return ans


import math

class Solution:

	def findFloor(self, A, N, X):
		start = 0
		end = N - 1
		f = -1
		while start <= end:
			mid = (start + end) // 2
			if A[mid] > X:
				end = mid - 1
			elif A[mid] < X:
				start = mid + 1
				f = mid
			else:
				f = mid
				break
		return f


class Solution:

	def findFloor(self, A, N, X):
		a = []
		for i in A:
			if i <= X:
				a.append(i)
		if len(a) == 0:
			return '-1'
		else:
			return A.index(a[len(a) - 1])


class Solution:

	def findFloor(self, A, N, X):
		max = -1
		index = -1
		for i in range(N):
			if A[i] <= X and A[i] > max:
				max = A[i]
				index = i
			elif A[i] > X:
				return index
		return index


class Solution:

	def findFloor(self, A, N, X):
		for i in range(len(A) - 1):
			if A[i] <= X and A[i + 1] > X:
				return i
		if A[-1] <= X:
			return len(A) - 1
		else:
			return -1


class Solution:

	def findFloor(self, A, N, X):
		return self.find_floor(A, N, X, 0, N - 1, -1)

	def find_floor(self, arr, n, x, l, h, res):
		if l > h:
			return res
		mid = l + (h - l) // 2
		if arr[mid] == x:
			return mid
		elif arr[mid] < x:
			res = mid
			return self.find_floor(arr, n, x, mid + 1, h, res)
		else:
			return self.find_floor(arr, n, x, l, mid - 1, res)


class Solution:

	def floorSearch(self, arr, low, high, x):
		if low > high:
			return -1
		if x >= arr[high]:
			return high
		mid = int((low + high) / 2)
		if arr[mid] == x:
			return mid
		if mid > 0 and arr[mid - 1] <= x and (x < arr[mid]):
			return mid - 1
		if x < arr[mid]:
			return self.floorSearch(arr, low, mid - 1, x)
		return self.floorSearch(arr, mid + 1, high, x)

	def findFloor(self, A, N, X):
		return self.floorSearch(A, 0, N - 1, X)


class Solution:

	def findFloor(self, A, N, X):
		a = A
		K = X
		dau = 0
		dau = 0
		cuoi = len(a)
		giua = int(cuoi / 2)
		if a[int(len(a) / 2)] > K:
			cuoi = giua + 1
		else:
			dau = giua - 1
		for i in reversed(range(dau, cuoi)):
			if K >= a[i]:
				return i
		return -1


class Solution:

	def findFloor(self, A, N, X):
		low = 0
		high = len(A) - 1
		floor = -1
		while low <= high:
			mid = (low + high) // 2
			if A[mid] <= X:
				floor = mid
				low = mid + 1
			else:
				high = mid - 1
		return floor


class Solution:

	def findFloor(self, arr, N, X):
		l = 0
		h = N - 1
		if len(arr) == 1 and arr[0] <= X:
			return 0
		if arr[h] <= X:
			return h
		while l <= h:
			mid = (l + h) // 2
			if arr[mid] > X:
				h = mid - 1
			elif arr[mid] <= X and arr[mid + 1] <= X:
				l = mid + 1
			elif arr[mid] <= X and arr[mid + 1] > X:
				return mid
		return -1


class Solution:

	def findFloor(self, A, N, X):
		index = -1
		low = 0
		high = N - 1
		if A[N - 1] <= X:
			return N - 1
		else:
			while low <= high:
				mid = (low + high) // 2
				if A[mid] <= X:
					if mid == N - 1 or A[mid + 1] > X:
						index = mid
						return index
					else:
						low = mid + 1
				else:
					high = mid - 1
			return index


class Solution:

	def findFloor(self, A, N, X):
		l = 0
		h = N - 1
		maxiE = -1
		idx = -1
		while l <= h:
			m = (l + h) // 2
			if A[m] == X:
				maxiE = X
				idx = m
				break
			elif A[m] < X:
				if maxiE < A[m]:
					maxiE = A[m]
					idx = m
				l = m + 1
			else:
				h = m - 1
		return idx


class Solution:

	def findFloor(self, A, N, X):
		start = 0
		end = N - 1
		floor = -1
		while start <= end:
			mid = start + (end - start) // 2
			if A[mid] == X:
				return mid
			elif A[mid] > X:
				end = mid - 1
			elif A[mid] < X:
				floor = mid
				start = mid + 1
		return floor


class Solution:

	def findindex(self, arr, i, j, k):
		if j < i:
			return j
		m = (i + j) // 2
		if arr[m] == k:
			return m
		elif arr[m] > k:
			return self.findindex(arr, i, m - 1, k)
		else:
			return self.findindex(arr, m + 1, j, k)

	def findFloor(self, A, N, X):
		if A[0] > X:
			return -1
		else:
			return self.findindex(A, 0, N - 1, X)


class Solution:

	def findFloor(self, A, N, X):
		(i, j) = (0, N - 1)
		while i <= j:
			mid = (i + j) // 2
			if A[mid] == X:
				return mid
			if A[mid] < X:
				i = mid + 1
			else:
				j = mid - 1
		return j


class Solution:

	def findFloor(self, A, N, X):
		s = 0
		e = N - 1
		mid = s + (e - s) // 2
		ans = -1
		while s <= e:
			if A[mid] <= X:
				ans = mid
				s = mid + 1
			else:
				e = mid - 1
			mid = s + (e - s) // 2
		return ans


class Solution:

	def findFloor(self, A, N, X):
		a = None
		for i in range(N - 1, 0, -1):
			if A[i] <= X:
				a = i
				break
		if a == None:
			return -1
		else:
			return a


class Solution:

	def findFloor(self, A, N, X):
		(lo, hi) = (0, len(A) - 1)
		while lo <= hi:
			mid = (lo + hi) // 2
			midnum = A[mid]
			if midnum == X:
				return mid
			elif midnum > X:
				hi = mid - 1
			elif midnum < X:
				lo = mid + 1
		if hi >= 0:
			return hi
		return -1


class Solution(object):

	def findFloor(self, nums, N, X):
		(left, right) = (0, N - 1)
		result = -1
		while left <= right:
			mid = left + (right - left) // 2
			val = nums[mid]
			if val == X:
				return mid
			elif val < X:
				result = mid
				left = mid + 1
			else:
				right = mid - 1
		return result


class Solution:

	def findFloor(self, arr, N, x):
		start = 0
		end = N - 1
		result = -1
		while start <= end:
			mid = (start + end) // 2
			if arr[mid] <= x:
				result = mid
				start = mid + 1
			else:
				end = mid - 1
		return result


class Solution:

	def findFloor(self, A, N, X):
		b = -1
		for i in range(N):
			if A[i] <= X:
				b = i
			elif A[i] > X:
				break
		return b


class Solution:

	def findFloor(self, a, n, x):
		(maxx, pos) = (-1, -1)
		for i in range(n):
			if a[i] <= x:
				maxx = max(maxx, a[i])
				pos = i
		return pos


class Solution:

	def findFloor(self, A, N, X):
		l = []
		for i in range(N):
			if A[i] <= X:
				l.append(i)
		if len(l) == 0:
			return -1
		else:
			return l[-1]


class Solution:

	def findFloor(self, A, N, X):
		if A[0] > X:
			return -1
		if A[-1] <= X:
			return N - 1
		index = 0
		while index < N:
			if A[index] > X:
				return index - 1
			index += 1


class Solution:

	def findFloor(self, A, N, X):
		maxi = 0
		ind = -1
		for i in range(N):
			if A[i] <= X:
				maxi = max(A[i], maxi)
		for i in range(N):
			if A[i] == maxi:
				ind = i
		return ind