Find Low/High Index

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

Solution Explanation

Runtime complexity

Since we are using binary search, the runtime complexity is logarithmic, O(logn).

Memory complexity

The memory complexity is constant, O(1) since no extra storage is being used.

Solution Breakdown

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;

once for finding the low index.
once for finding the high index.

Low 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.

High index

Similarly, we can find the high index by slightly modifying the above condition:

switch the low index to mid + 1 when element at mid index is less than or equal to the key.
switch the high index to mid - 1 when the element at mid is greater than the key.

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

Find Low/High Index

Problem Statement

Hint

Try it yourself