PROBLEM STATEMENT:
We are given a sorted list and an element x. We need to find the first index and last index of x in the list or report that x doesn't exist in the array.
ALGORITHM FOR FIRST OCCURRENCE:
1. First find the middle element.
2. If the middle element is equal to x, then store the middle index as the answer and search for the element in the left part from the middle index.
3. If the element is greater than the middle element, search for the element in the right part from the middle index.
4. If the element is less than the middle element, search for the element in the left part from the middle index.
5. Continue the process until only one element is left.
ALGORITHM FOR LAST OCCURRENCE:
1. First find the middle element.
2. If the middle element is equal to x, then store the middle index as the answer and search for the element in the right part from the middle index.
3. If the element is greater than the middle element, search for the element in the right part from the middle index.
4. If the element is less than the middle element, search for the element in the left part from the middle index.
5. Continue the process until only one element is left.
CODE:
#include <bits/stdc++.h>
using namespace std;
int firstoccurance(int x,int l,int r,int a[],int firstans)
{
if(r>=l){
int middle=l+(r-l)/2;
if(x==a[middle])
{
firstans= middle;
firstoccurance(x,l,middle-1,a,firstans);
}
else if(x>a[middle])
firstoccurance(x,middle+1,r,a,firstans);
else if(x<a[middle])
firstoccurance(x,l,middle-1,a,firstans);
}
else
return firstans;
}
int lastoccurance(int x,int l,int r,int a[],int lastans)
{
if(r>=l){
int middle=l+(r-l)/2;
if(x==a[middle])
{
lastans= middle;
lastoccurance(x,middle+1,r,a,lastans);
}
else if(x>a[middle])
lastoccurance(x,middle+1,r,a,lastans);
else if(x<a[middle])
lastoccurance(x,l,middle-1,a,lastans);
}
else
return lastans;
}
int main()
{
int n; //size of array
cin>>n;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
int x;
cin>>x;//element to be searched
int firstans=-1,lastans=-1;
firstans=firstoccurance(x,0,n-1,a,firstans); //return the first index of x in a[]
lastans=lastoccurance(x,0,n-1,a,lastans); //return the last index of x in a[]
cout<<firstans<<endl<<lastans<<endl;
return 0;
}
INPUT:
10
1 2 2 2 2 6 7 9 11 12
2
OUTPUT:
1
4
0 Comments