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