Найти элемент поворота в отсортированном и повернутом массиве

Question

Я пытаюсь найти элемент pivot в отсортированном и повернутом массиве, который возвращает. Это дает ошибку stackoverflow.

Ниже приведен код:

int findPivot(int[] arr,int lo, int hi) {

    int mid = lo +(hi-lo)/2;

    if(arr[mid]>arr[mid+1]) {
        return mid;
    }
    else if (arr[mid]<arr[hi]) {
        return findPivot(arr,lo,mid-1);
    }else {
        return findPivot(arr,mid+1,hi);
    }

}

Как мне решить эту проблему?

Answer 1

вам не хватает базовых условий.

int findPivot(int arr[], int low, int high) 
{ 
  // base cases 
  if (high < low) return -1; 
  if (high == low) return low; 

  int mid = (low + high)/2; /*low + (high - low)/2;*/
  if (mid < high && arr[mid] > arr[mid + 1]) 
   return mid; 

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

 if (arr[low] >= arr[mid]) 
  return findPivot(arr, low, mid-1); 

 return findPivot(arr, mid + 1, high); 
}