The question was to find Floor in a Sorted Array and my code is not passing on the runtime test case. Please help me out here by telling me an optimized approach (it would be nice to find an answer without the use of STL Libraries).

This Here is my code:

int findFloor(vector<long long> v, long long n, long long x)
{
    long long start = 0, end = n - 1;
    long long res = -1;

    while (start <= end)
    {
        long long mid = start   (end - start) / 2;

        if (v[mid] == x)
        {
            res = v[mid];
        }
        else if (v[mid] < x)
        {
            res = v[mid];
            start = mid   1;
        }
        else if (v[mid] > x)
        {
            end = mid - 1;
        }
    }

    return res;
}

CodePudding user response：

I think I found a problem, so..

Let's say we have an array, that contains [1, 2, 3, 4, 5] these numbers and we're finding the number 4 in it (x = 4).

In our case:

start = 0; end = 4; mid = 2;

At the first iteration, v[mid] < x and start = mid 1 (3)

At the second iteration start = 3, end = 4, mid = 3, so v[3] == 4 this is true, you set res = v[mid] and after that start is always 3 and the loop runs endlessly, you need to break the loop

CodePudding user response：

(it would be nice to find an answer without the use of STL Libraries)

If so then I would write an iterative binary search this way while keeping the algorithm very simple:

#include <iostream>
#include <cstddef>


[[ nodiscard ]] constexpr std::ptrdiff_t
binarySearch( const long long* const array,
              std::ptrdiff_t lowerBound,
              std::ptrdiff_t upperBound,
              const long long target) noexcept
{
    std::ptrdiff_t result { };

    while ( lowerBound <= upperBound )
    {
        std::ptrdiff_t mid { lowerBound   ( upperBound - lowerBound ) / 2 };

        if ( array[ mid ] == target )
        {
            return result = mid;
        }
        else if ( array[ mid ] < target )
        {
            lowerBound = mid   1;
        }
        else
        {
            upperBound = mid - 1;
        }
    }

    return result = -1;
}

int main( )
{
    const long long arr[] { 3, 44, 44, 1000, 1050 };
    const std::ptrdiff_t lowerBound { 0 };
    const std::ptrdiff_t upperBound { std::ssize( arr ) - 1 };
    const long long target { 1000 };

    std::ptrdiff_t resultIndex { binarySearch( arr, lowerBound,
                                               upperBound, target ) };

    if ( resultIndex == -1 )
    {
        std::cout << "The element <<" << target
                  << ">> is not present in the array\n";
    }
    else
    {
        std::cout << "The element <<" << target << ">> is present at index "
                  << resultIndex << " of the array\n";
    }
}

Sample input/output:

The element <<1000>> is present at index 3 of the array

Note: The above code snippet only compiles using C 20 (live).

The above code also works with other contiguous container types such as std::vector, std::array, etc.

Note: Some of the keywords used above (such as [[ nodiscard ]], constexpr, noexcept) can be removed without causing an issue. However I put them there for the sake of robustness.