If mid is greater than key , all elements in range [ mid + 1 , high ] are >= key we note down the last found index , then we search in left side of mid so we now search in [ low , mid - 1 ]
ans = mid ; high = mid - 1 ; } else if ( midVal == key ) {