Find Low/High Index

Table of Contents

Problem Statement Hint Try it yourself Solution Solution Explanation Runtime complexity Memory complexity Solution Breakdown Low index High index

Home/

Blog/

Interview Prep/

Find Low/High Index

1 min read

Oct 15, 2025

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.