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
# 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
# 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)
