I am trying to find the minimum element in an array that has been sorted and rotated (Edit: distinct elements).

I wrote a function that uses binary search, splitting the array into smaller components and checking whether the "mid" value of the current component was either greater than the "high" value or lesser than the "starting" value moves towards either end because by my rough logic, the smallest element must be "somewhere around there".

Thinking about it a little harder, I realized that this function would not return the correct answer for a fully sorted component/array, but for some reason, it does.

// Function to find the minimum element in sorted and rotated array.
int minNumber(int arr[], int low, int high)
{
    int mid = (low   high) / 2;

    if (low > high)
        return -1;

    if (low == high)
        return arr[low];

    if (mid == 0 || arr[mid - 1] > arr[mid])
        return arr[mid];
    else if (arr[mid] > arr[high])
    {
        return (minNumber(arr, mid   1, high));
    }
    else if (arr[mid] < arr[low])
    {
        return (minNumber(arr, low, mid - 1));
    }
}

Passing the array "1,2,3,4,5,6,7,8,9" through it returns 1. I though maybe the rax register might have accidentally stored a 1 at some point and now the function was just spitting it out as there was no valid return statement for it to go through. Running it through g debugger line-by-line didn't really help and I'm still confused as to how this code works.

FULL CODE

// { Driver Code Starts
#include <bits/stdc  .h>
using namespace std;

// } Driver Code Ends

class Solution
{
public:
    // Function to find the minimum element in sorted and rotated array.
    int minNumber(int arr[], int low, int high)
    {
        int mid = (low   high) / 2;

        if (low > high)
            return -1;

        if (low == high)
            return arr[low];

        if (mid == 0 || arr[mid - 1] > arr[mid])
            return arr[mid];
        else if (arr[mid] > arr[high])
        {
            return (minNumber(arr, mid   1, high));
        }
        else if (arr[mid] < arr[low])
        {
            return (minNumber(arr, low, mid - 1));
        }
    }
};

// { Driver Code Starts.

int main()
{

    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        int a[n];
        for (int i = 0; i < n;   i)
            cin >> a[i];
        Solution obj;
        cout << obj.minNumber(a, 0, n - 1) << endl;
    }
    return 0;
} // } Driver Code Ends

CodePudding user response：

Short answer: Undefined behavior doesn't mean it can't give the right answer.

<source>: In member function 'int Solution::minNumber(int*, int, int)':
<source>:31:5: warning: control reaches end of non-void function [-Wreturn-type]

When the array isn't rotated you hit that case and you are simply getting lucky.

Some nitpicking:

• turn on the compiler warnings and read them
• int is too small for a large array
• int mid = (low high) / 2; is UB for decently sized arrays, use std::midpoint
• minNumber should take a std::span and then you could use std::size_t size = span.size();, span.first(size / 2) and span.last(size - size / 2)