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.

Unmitigated · Accepted Answer · 2022-07-23 19:13:14Z

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, 2022 at 19:13

Unmitigated

91.4k12 gold badges102 silver badges109 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Learner Over a year ago

In this line low + high >>> 1 what the 3 arrows indicate, how they work.

Unmitigated Over a year ago

@learner It is the same as adding low and high, then dividing by 2, but it avoids overflow issues.

andrewJames Over a year ago

@learner : what does ">>>" mean in java?

Collectives™ on Stack Overflow

Find index in array based on given value

1 Answer 1

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related