Given a list of number, Find Starting and Ending Index of a Key in a Sorted List where there may be duplicate items in it.
Example
int [] nums = {2,5,6,8,8,8,8,9,9,9,10,13,13,13,40};
k=9
Ans: 7,9
Explanation: We can find 9 in the list at index 7,8 and 9 but we only need the starting and ending index.
Solution:
Any time we are asked to find an element inside a sorted array, we should think of a binary search (O(logn)) as it faster than linear search(O(N)).
Therefore, we will do a simple binary search on the given key and we then iterate backwards till we find the smallest index we can find this number and iterate forward to find the largest index we can find this number.
public static int FindLow(int [] nums, int k) {
int index = BSearch(0, nums.Length-1, nums,k);
int i = index;
while(nums[i] == k) {
i--;
}
return i+1;
}
public static int FindHigh(int [] nums, int k) {
int index = BSearch(0, nums.Length-1, nums,k);
int i = index;
if(i==nums.Length-1)
return i;
while(nums[i] == k) {
i++;
}
return i-1;
}
public static int BSearch(int low, int high, int [] nums, int k) {
if(low > high) return -1; //base case
int mid = (low + high)/2;
if(nums[mid] < k)
return BSearch(mid+1, high, nums, k);
else if(nums[mid] > k)
return BSearch(low, mid, nums, k);
else
return mid;
}