First & last positions of an element in a sorted array

Nov. 16, 2020 116

Problem Statement

Given a sorted array with duplicate elements, the task is to find the starting and ending indices of the given element. Let’s understand by example.

Input :

A[ ] = { 1, 2, 3, 3, 4, 4, 4, 5 }
item= 4

Output :

Starting index - 4
Ending index - 6

Solution

Naive Approach

A brute force solution would be to run a loop, keeping two variables FIRST and LAST, update FIRST after getting the first occurrence of the element and keep updating the LAST variable till the element pointed by the loop is the same as the given element. At the end of the iteration, FIRST will have the index of the first occurrence of the given element and LAST will have the last index of the given element.

Complexity analysis

As we are iterating the array once, the time complexity for the above approach is $O(\text{Size of the array})$.

Pseudocode for the above approach

LAST = -1, FIRST = -1
for i = 0 to i = size of array - 1
if a[i] == item
{
if ( FIRST == -1 )
FIRST = i
LAST = i
}
print FIRST, LAST


Implementation of the above approach

• C/C++
• Python
#include <bits/stdc++.h>
using namespace std;

// variables for storing first and
// last index of the given element
// in the array

int FIRST = -1, LAST = -1;

// function for calculating the first
// and last index of the given element
// in the array

void find_index(int a[], int n, int item)
{
for (int i = 0; i < n; i++)
if (a[i] == item)
{
if (FIRST == -1)
FIRST = i;
LAST = i;
}
}

// Driver code

int main()
{
int a[] = {1, 2, 3, 3, 4, 4, 4, 5};

int n = sizeof(a) / sizeof(int);
int item = 4;

// function call

find_index(a, n, item);

cout << "Starting index " << FIRST << "\n"
<< "Last index " << LAST;
}

# variables for storing first and
# last index of the given element
# in the array

FIRST = -1
LAST = -1

# function for calculating the first
# and last index of the given element
# in the array

def find_index(a, n, item):
global FIRST
global LAST
for i in range(n):
if a[i] == item:
LAST = i
if FIRST == -1:
FIRST = i

# Driver code

a = [1, 2, 3, 3, 4, 4, 4, 5]

n = len(a)

item = 4

# function call

find_index(a, n, item)

print("Starting index", FIRST, "\nLast index", LAST)


An efficient approach using Binary Search

We can use binary search to solve the problem by modifying the classical algorithm a little bit as per our requirements.

We will write two functions separately for calculating the first and last indices.

We will search the given element in the array using normal binary search logic and then,

For calculating the first index :
The logic for calculating the first index is that on finding the element, we will reduce our search space to the left and update FIRST with the current index.

For calculating the last index :
The logic for calculating the last index is that on finding the element, we will reduce our search space to the right and update LAST with the current index.

Complexity analysis

Time complexity for the above approach will be the same as that of binary search. For an array of size N, the time complexity will be $O(N\log{N})$

Pseudocode for the above approach (for the first index)

low = 0, high = size - 1
FIRST = -1

while low <= high
{
mid = (low + high) / 2
if a[mid] > item, high = mid - 1
else if a[mid] < item, low = mid + 1
else
{
FIRST = mid
high = mid-1
}
}

print FIRST

for calculating the last index :

low = 0, high = size - 1
LAST = -1

while low <= high
{
mid= (low + high) / 2
if a[mid] > item, high = mid - 1
else if a[mid] < item, low = mid + 1
else
{
LAST = mid
low = mid + 1
}
}

print LAST


Implementation of the above approach

• C/C++
• Python
#include <bits/stdc++.h>

using namespace std;

// function for calculating the first
// index of the given element
// in the array

int first_index(int a[], int n, int item)
{
int low = 0, high = n - 1;
int FIRST = -1;

while (low <= high)
{
int mid = (low + high) / 2;
if (a[mid] > item)
high = mid - 1;
else if (a[mid] < item)
low = mid + 1;
else
{
FIRST = mid;
high = mid - 1;
}
}

return FIRST;
}

// function for calculating the last
// index of the given element
// in the array

int last_index(int a[], int n, int item)
{
int low = 0, high = n - 1;
int LAST = -1;

while (low <= high)
{
int mid = (low + high) / 2;
if (a[mid] > item)
high = mid - 1;
else if (a[mid] < item)
low = mid + 1;
else
{
LAST = mid;
low = mid + 1;
}
}

return LAST;
}

// Driver code

int main()
{
int a[] = {1, 2, 3, 3, 4, 4, 4, 5};

int n = sizeof(a) / sizeof(int);
int item = 4;

// function call

int FIRST = first_index(a, n, item);
int LAST = last_index(a, n, item);

cout << "Starting index " << FIRST << "\n"
<< "Last index " << LAST;
}

# function for calculating the first
# index of the given element
# in the array

def first_index(a, n, item):

low = 0
high = n - 1
FIRST = -1

while low <= high:
mid = int((low + high) / 2)
if a[mid] > item:
high = mid - 1
elif a[mid] < item:
low = mid + 1
else:
FIRST = mid
high = mid - 1

return FIRST

# function for calculating the last
# index of the given element
# in the array

def last_index(a, n, item):

low = 0
high = n - 1
LAST = -1

while low <= high:
mid = int((low + high) / 2)
if a[mid] > item:
high = mid - 1
elif a[mid] < item:
low = mid + 1
else:
LAST = mid
low = mid + 1

return LAST

# Driver code

a = [1, 2, 3, 3, 4, 4, 4, 5]

n = len(a)

item = 4

# function call

FIRST = first_index(a, n, item)
LAST = last_index(a, n, item)

print("Starting index", FIRST, "\nLast index", LAST)


Liked the post?
Editor's Picks
0 COMMENT