public class MyClass {
    public static void main(String args[]) {
      
      String[] arr = new String[3];
      arr[0]="A";arr[1]="Abet";arr[2]="akind";
      
      System.out.println(findLowestIndexPrefix(arr,"a"));
      System.out.println(findLowestIndexPrefix(arr,"b"));
      System.out.println(findLowestIndexPrefix(arr,"Ak"));
      System.out.println(findLowestIndexPrefix(arr,"ak"));
      
    }
    
    public static int findLowestIndexPrefix(String[] arr, String key) {
        int minIdx = Integer.MAX_VALUE;
        int low=0,high=arr.length-1;
        
        while(low<=high) {
            int mid = low + (high-low)/2;
            String middle = arr[mid];
            int compare = compareKeys(key,middle);
            
            if (compare == 0) {
                minIdx = Math.min(minIdx,mid);
                // still continue to do binary search
                high = mid-1;
            } else if (compare==-1) {
                // key is less than middle
                high = mid-1;
            } else {
                // key is greater than middle
                low = mid+1;
            }
            
        }
        
        if (minIdx == Integer.MAX_VALUE) return -1;
        return minIdx;
    }
    
    private static int compareKeys(String s1,String s2) {
        
        int minL = Math.min(s1.length(),s2.length());
        String sub1 = s1.substring(0,minL);
        String sub2 = s2.substring(0,minL);
        return sub1.compareTo(sub2);
        
    }
}