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 ) . Suggestions are welcomed as always had been.