Given a sorted array of integers, return the low and high index of the given key. You must return -1 if the indexes are not found.
The array length can be in the millions with many duplicates.
In the following example, according to the the key
, the low
and high
indices would be:
key
: 1, low
= 0 and high
= 0
key
: 2, low
= 1 and high
= 1
key
: 5, low
= 2 and high
= 9
key
: 20, low
= 10 and high
= 10
For the testing of your code, the input array will be:
1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 6, 6
int find_low_index(vector<int>& arr, int key) { int low = 0; int high = arr.size() - 1; int mid = high / 2; while (low <= high) { int mid_elem = arr[mid]; if (mid_elem < key) { low = mid + 1; } else { high = mid - 1; } mid = low + (high - low) / 2; } if (low < arr.size() && arr[low] == key) { return low; } return -1; } int find_high_index(vector<int>& arr, int key) { int low = 0; int high = arr.size()-1; int mid = high/2; while (low <= high) { int mid_elem = arr[mid]; if (mid_elem <= key) { low = mid+1; } else { high = mid-1; } mid = low + (high-low)/2; } if(high == -1) return high; if (high < arr.size() && arr[high] == key) { return high; } return -1; } int main(int argc, char* argv[]) { { vector<int> arr = {1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 6, 6}; int key = 5; int low = find_low_index(arr, key); int high = find_high_index(arr, key); cout << "Low Index of " << key << ": " << low <<endl; cout << "High Index of " << key << ": "<< high <<endl; key = -2; low = find_low_index(arr, key); high = find_high_index(arr, key); cout << "Low Index of " << key << ": "<< low <<endl; cout << "High Index of " << key << ": "<< high <<endl; } }
Since we are using binary search, the runtime complexity is logarithmic, O(logn).
The memory complexity is constant, O(1) since no extra storage is being used.
Linearly scanning the sorted array for low
and high
indices are highly inefficient since our array size can be in millions.
Instead, we will use a slightly modified binary search to find the low
and high
indices of a given key.
We need to do binary search twice;
low
index.high
index.Let’s look at the algorithm for finding the low
index:
At every step, consider the array between low
and high
indices and calculate the mid
index.
If the element at mid
index is less than the key
, low
becomes mid + 1
(to move towards the start of range).
If the element at mid is greater or equal to the key
, the high
becomes mid - 1
. Index at low
remains the same.
When low
is greater than high
, low
would be pointing to the first occurrence of the key
.
If the element at low
does not match the key
, return -1
.
Similarly, we can find the high
index by slightly modifying the above condition:
low
index to mid + 1
when element at mid
index is less than or equal to the key
.high
index to mid - 1
when the element at mid
is greater than the key
.