LOHIGH - Editorial

LOHIGH: Editorial

Problem-code: LOHIGH

Contest-Code: CSMH2021

Author: M RAHUL

Editorialist: M RAHUL

DIFFICULTY: EASY

PREREQUISITES:

Basic observations, Binary Seaarch Algorithm

PROBLEM:

Given a sorted array of integers of size ‘n’, return the low and high index of the given key. You must print -1 as low and high if the indexes are not found. The array length can be in the millions with many duplicates, so kindly use the algorithm which helps to reduce time.

EXPLANATION:

Here you’re given a sorted array of size ‘n’. As mentioned in the problem that the length of rray can be in millions and it is sorted then the efficient approach for finding the index of first and last occurence of element is binary search approach. Write two functions one for finding starting index and other for finding last index of occurence of the given element.

SOLUTION:

#include<bits/stdc++.h>
using namespace std;
int Low_ind(int arr[],int n, int key) {
int low = 0;
int high = n - 1;
int mid = high / 2;

while (low <= high) {
int m = arr[mid];

if (m < key) {
  low = mid + 1;
}
else {
  high = mid - 1;
}

mid = low + (high - low) / 2;

}

if (low <n && arr[low] == key) {
return low;
}

return -1;
}

int High_ind(int arr[], int n, int key) {
int low = 0;
int high = n-1;
int mid = high/2;

while (low <= high) {

int m = arr[mid];

if (m <= key) {
  low = mid+1;
}
else {
  high = mid-1;
}

mid = low + (high-low)/2;

}

if(high == -1)
return high;

if (high <n && arr[high] == key) {
return high;
}

return -1;
}

int main() {
int n;
cin>>n;
int key,arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];
cin>>key;
int low = Low_ind(arr,n, key);
int high = High_ind(arr,n, key);
cout<<low<<" "<<high;
}

Feel free to Share your approach, if you want to. (even if its same :stuck_out_tongue: ) . Suggestions are welcomed as always had been. :slight_smile: