Search code examples
javarecursionbinary-search

Recursion binary search for a double-ordered array

Given an array of n different numbers that are strictly increasing from index 0 to m, and strictly decreasing from index m to index n-1, I want to use recursion to find the index m of the largest number in the array. My method needs to run proportionally to O(log n)

So far I thought of using binary search recursion algorithm, which would indeed run in the given time complexity I believe, and came up with the following;

/* 
 * @param inputArr     -> input array of numbers over which the reccursive method is called 
 * @param head   -> the first index of the array passed as argument
 * @param tail     -> the last index of the array passed as argument
 * @returns max    -> index for the maximum of the ascending sequence
 */
public static int largestNumber(int[] inputArr, int head, int tail) {
    //base cases for recursion to stop
    if(head==tail)
        return head;

    int midIndex = (tail + head)/2;
    
    // the maximum is at the mid index
    if(inputArr[midIndex] > inputArr[midIndex +1] && inputArr[midIndex] < inputArr[midIndex -1]) {
        return midIndex;
    } else {
        
        // the maximum is not at the mid index
        if (inputArr[midIndex+1] > inputArr[midIndex]) {
            return largestNumber(inputArr, midIndex+1, tail);
        } else {
            return largestNumber(inputArr, head, midIndex - 1);
        }
    }

The outputs for this are

enter image description here

which are all incorrect (it should be 0 , 3, 2, 4 form the top to bottom), suggesting I mishandled either my base case or the conditional statements. Does anyone have any hint on where I possibly went wrong or what case I am missing? In my mind my function seems to be complete...

Solution

  • One thing I see is that you're comparing inputArr[midIndex] > inputArr[midIndex - 1] but inputArr[midIndex] < inputArr[midIndex - 1]. To return the max, you want inputArr[midIndex] to be larger than the elements on both sides.

    You are also accessing an illegal array index when head == 0 and tail == 1.