Find index in array based on given value-CodePudding

I have a sorted array of numbers with array length as n. For a given item k find index i in the sorted array where elements from index i to n are greater than the given item k. If there is no index present then return -1

This is my program:

public static int getIndex(int[] arr, int k) {
     int x = -1;
     for(int i=0; i<arr.length; i  ) {
       if(arr[i] > k) {
           x = i; break;
       }
     }
     return x;
}

The time complexity of this approach is O(n), and I want to reduce it further.

CodePudding user response：

Since the array is sorted, use binary search for a time complexity of O(log N).

public static int getIndex(int[] arr, int k) {
    int low = 0, high = arr.length - 1;
    while (low <= high) {
        int mid = low   high >>> 1;
        if(arr[mid] > k) high = mid - 1;
        else low = mid   1;
    }
    return low == arr.length ? -1 : low;
}