Okay, so floor of a number in an array is defined as the largest number in the array that is lower than the provided number. If we find it in the array, we return its index, otherwise -1.

For example, arr = {1, 2, 4, 4, 4, 6, 8, 10, 12}.
Case 1, target = 4. Output is 1 (as arr[1] is the largest number smaller than target).
Case 2, target = 13. Output is 8 (as arr[8] is the largest number smaller than target).
Case 3, target = 0. Output is -1 (as there is no element greater than 0).

For an array that does not have any duplicates, it is just a binary search and returning high-1 and we get a time complexity of O(n).

But for an array that has duplicates, after performing binary search, the time complexity tends to O(n) as I have to linearly traverse back to get the the smallest element that is not equal to target itself.

For example, arr = {1, 2, 4, 4, 4, 6, 8, 10, 12}.
Case 1, target = 4.
Binary search gives me index 4 as arr[4] = 4. But I have to traverse back to get the largest number smaller than target.

Is there something that can help me remove the linear searching and just have log2(n) time complexity?