Problem: In a given sorted array, find the greatest element which is less than a given number x.
Example:
Input: arr = [7, 12, 16, 20, 24 29], x = 22 Output: 20
Approach: A simple change in binary search will work here.
Implementation in C#:
public static int BinarySearch(int[] arr, int x)
{
int low = -1, high = arr.Length - 1;
while(low + 1 < high)
{
int mid = low + (high - low) / 2;
if(arr[mid] <= x) // the change required
{
low = mid;
}
else
{
high = mid;
}
}
return arr[low];
}
Complexity: O(logn)
