Minimum index i such that all the elements from index i to given index are equal | C ++ implementation of the approach ; Function to return the minimum required index ; Short - circuit more comparisions as found the border point ; For cases were high = low + 1 and arr [ high ] will match with arr [ pos ] but not arr [ low ] or arr [ mid ] . In such iteration the if condition will satisfy and loop will break post that low will be updated . Hence i will not point to the correct index . ; Driver code ; cout << minIndex ( arr , 2 ) << endl ; Should be 1 cout << minIndex ( arr , 3 ) << endl ; Should be 1 cout << minIndex ( arr , 4 ) << endl ; Should be 4
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minIndex ( int arr [ ] , int pos ) { int low = 0 ; int high = pos ; int i = pos ; while ( low < high ) { int mid = ( low + high ) / 2 ; if ( arr [ mid ] != arr [ pos ] ) { low = mid + 1 ; } else { high = mid - 1 ; i = mid ; if ( mid > 0 && arr [ mid - 1 ] != arr [ pos ] ) { break ; } } } return arr [ low ] == arr [ pos ] ? low : i ; } int main ( ) { int arr [ ] = { 2 , 1 , 1 , 1 , 5 , 2 } ; return 0 ; }