Search Range Editorial

Practice Problem Link: Search Range | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a sorted array and a number key, find the index of the first and last occurrence of the key in the array.

If the key is not present return [-1, -1].

Naive Approach

A simple solution is to iterate the array and return the first and last occurrence of the key and if the key is not present return [-1, -1].

Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Implementation

C++

vector<int> searchRange(vector<int> &arr, int key) {
   int first = -1, last = -1;
   for (int i = 0; i < arr.size(); i++) {
       if (first == - 1 && key == arr[i]) {
           first = i;
       }
       if (key == arr[i]) {
           last = i;
       }
   }
   vector<int> indexes = {first, last};
   return indexes;
}

Java

class Solution {
   int[] searchRange (int[] arr, int key) {
       int first = -1, last = -1;
       for (int i = 0; i < arr.length; i++) {
           if (first == -1 && key == arr[i]) {
               first = i;
           }
           if (key == arr[i]) {
               last = i;
           }
       }
       int[] indexes = {first, last};
       return indexes;
   }
} 

Optimal Approach

Since the array is sorted we can find the first and last indexes of the key using binary search.

As the element just before the first occurrence must be less than the key and the element just after the last occurrence must be greater than the key.

The first and last indexes can be found separately using two different binary search functions.

To find the first occurrence:

• Initialize four variables high = n-1, low = 0 and mid.
• Perform a binary search until (high >= low). Assign mid = (high + low) / 2.
• If arr[mid - 1] is less than key and arr[mid] is equal to key return mid. Otherwise, if arr[mid]  is less than the key, search in the second half otherwise search in the first half.
• Return -1 as the default condition.

To find the last occurrence:

• Initialize three variables high = n-1, low = 0 and mid.
• Perform a binary search until (high >= low). Assign mid = (high + low) / 2.
• If arr[mid] is equal to key and arr[mid + 1] is greater than the key return mid. Otherwise, if arr[mid] is greater than the key, search in the first half otherwise search in the second half.
• Return -1 as the default condition.

Analysis

• Time Complexity: O(log(n))
• Space Complexity: O(1)

Implementation

C++

int findStart(vector<int> arr, int low, int high, int key) {
   if (high >= low) {
       int mid = (high + low) / 2;
       if ((mid == 0 || key > arr[mid - 1]) && arr[mid] == key) {
           return mid;
       } else if (key > arr[mid]) {
           return findStart (arr, mid + 1, high, key);
       } else {
           return findStart (arr, low, mid - 1, key);
       }
   }
   return - 1;
}
int findEnd(vector<int> arr, int low, int high, int key, int n) {
   if (high >= low) {
       int mid = (high + low) / 2;
       if ((mid == n - 1 || key < arr[mid + 1]) && arr[mid] == key) {
           return mid;
       } else if (key < arr[mid]) {
           return findEnd (arr, low, mid - 1, key, n);
       } else {
           return findEnd (arr, mid + 1, high, key, n);
       }
   }
   return - 1;
}
vector<int> searchRange(vector<int> &arr, int key) {
   int n = arr.size();
   vector<int> indexes = {findStart (arr, 0, n - 1, key), findEnd (arr, 0, n - 1, key, n)};
   return indexes;
}

Java

class Solution {
   int findStart (int[] arr, int low, int high, int key) {
       if (high >= low) {
           int mid = (high + low) / 2;
           if ((mid == 0 || key > arr[mid - 1]) && arr[mid] == key) {
               return mid;
           } else if (key > arr[mid]) {
               return findStart(arr, mid + 1, high, key);
           } else {
               return findStart(arr, low, mid - 1, key);
           }
       }
       return -1;
   }
   int findEnd (int[] arr, int low, int high, int key, int n) {
       if (high >= low) {
           int mid = (high + low) / 2;
           if ((mid == n - 1 || key < arr[mid + 1]) && arr[mid] == key) {
               return mid;
           } else if (key < arr[mid]) {
               return findEnd(arr, low, mid - 1, key, n);
           } else {
               return findEnd(arr, mid + 1, high, key, n);
           }
       }
       return -1;
   }
   int[] searchRange (int[] arr, int key) {
       int n = arr.length;
       int[] indexes = {findStart (arr, 0, n-1, key), findEnd(arr, 0, n-1, key, n)};
       return indexes;
   }
}