The code in the video fails this test case: {4,4,4,4,4,4,4,4,4,4,4,4,4,1,2,3}. This is because here a[mid]==a[s] but the right part of array is unsorted not the left part. The code considers left part to be unsorted when the two are equal. please provide the rectified solution.
Code fails test case
send the code given in video
correct code is:
#include
using namespace std;
int PivotIndex(int*arr,int n){
int si=0,ei=n-1;
while(si<=ei){
int mid=(si+ei)/2;
//case:1
if(arr[mid]<arr[mid-1]) return mid-1;
if(arr[mid]>arr[mid+1]) return mid;
if(arr[mid]>arr[si]){
/// right part is unsorted
si=mid+1;
}
if(arr[mid]<arr[ei]){
/// left part is unsorted
ei=mid-1;
}
}
}
int main() {
int n;
int arr[100];
cin>>n;
for(int i=0;i<n;i++){
cin>>arr[i];
}
cout<<PivotIndex(arr,n);
return 0;
}