Find index in array based on given value

Question

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.

score 1 · Accepted Answer · answered Jul 23 '22 at 19:13

1

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;
}

answered Jul 23 '22 at 19:13

Unmitigated

76,500
11
62
80

In this line `low + high >>> 1` what the 3 arrows indicate, how they work. – learner Jul 23 '22 at 19:21
@learner It is the same as adding low and high, then dividing by 2, but it avoids overflow issues. – Unmitigated Jul 23 '22 at 19:22
@learner : [what does ">>>" mean in java?](https://stackoverflow.com/q/19058859/12567365) – andrewJames Jul 23 '22 at 20:07

Find index in array based on given value

1 Answers1