Wednesday, March 2, 2022

Find the element in a sorted array which is equal or just less than given number

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)

No comments:

Post a Comment