I need a recursive algorithm to find the first negative numb

I need a recursive algorithm to find the first negative number A in an array of n integers that is monotonically decreasing, meaning that for every index from 0 to n2, we have that A[i]> A[i+ 1].

I also need to find the closed form of the recurrence. The algorithm should run in (log n) time. Please let me know if you can help

Solution

Hi, Please find my C++ code and Algorithm:

Please let me know in case of any issue:

#include <iostream>
using namespace std;

int firstNegativeNumber(int arr[], int low, int high){

   if(high >= low){

       int mid = (low + high)/2;

       if((mid == low && arr[mid] < 0) || (arr[mid-1] < 0 && arr[mid] >= 0))
           return mid-1;

       if((mid == high && arr[mid] < 0) || (arr[mid] >= 0 && arr[mid+1] < 0))
           return mid+1;

       if(arr[mid] >= 0) // go right
           return firstNegativeNumber(arr, mid+1, high);
       return firstNegativeNumber(arr, low, mid-1);
   }

   return -1;
}

int main(){

   int arr[] = {4,3,2,1,0,-1,-2,-3};

   cout<<firstNegativeNumber(arr, 0, 5)<<endl;

   return 0;
}

Algorithm:
   int firstNegativeNumber(int arr[], int low, int high){

       IF high >= low then do:

           mid <- (high+low)/2

           IF (mid == low and arr[mid] < 0) or (arr[mid-1] < 0 and arr[mid] >= 0) do
               return mid-1;
           IF (mid == high and arr[mid] < 0) or (arr[mid] >=0 and arr[mid+1] < 0) do
               return mid+1;

           IF arr[mid] >= 0 then do:
               call firstNegativeNumber(arr, mid+1, high)
           ELSE do:
               call firstNegativeNumber(arr, low, mid-1)

       ELSE
           return -1 ; // no negative number
   }