I am working with array where the set is sorted. The task is to find the range of a value.
Lets assume we have this sorted array:
int[] array = {1,1,1,3,3,9,10}
Example We have to find the range- min and max for the element 1. We quickly spot that the first index of the element 1 is 0, and the range max is 2.
We now know that the range between 0 and 2 all have value 1. If the searched element is 3 we see that range is 3-4, and for the element 9 the range is 6-6.
I have used linear search to do this, but would hear, if there is a more faster way to do this?
You can use two versions of binary search to find the leftmost and rightmost positions:
int[] array = { 1, 1, 1, 3, 3, 9, 10 }
int value = ...
int leftmost(int min, int max)
{
if (min == max) return min
int mid = (min + max) / 2
if (array[mid] < value) return leftmost(mid + 1, max)
else return leftmost(min, mid)
}
int rightmost(int min, int max)
{
if (min == max) return min
int mid = (min + max + 1) / 2
if (array[mid] > value) return rightmost(min, mid - 1)
else return rightmost(mid, max)
}
Just make the calls with min=0 and max=array.length-1. Time complexity is O(logn).
You will get outputs like this (0-based indexes):
value=1 -> left=0, right=2
value=3 -> left=3, right=4
value=9 -> left=5, right=5
value=10 -> left=6, right=6
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments