Find all indices of a given element in the sorted form of the given array

Sandeep kamila
Last Updated: May 13, 2022

Introduction

Problem statement

We are given an array and a value K. Our task is to find all indices of K in the sorted form ascending) of the given array. 

Sample examples

Input1:  a[] = [ 3, 5, 7, 9, 7, 2, 7] , K = 7

Output1:  3 4 5   // all indices of 7
 

Explanation:

Sorted array: 

Indices :

 

Input2: a[] = [ 2, 3, 6, 4, 3, 4, 0] , K = 3

Output2:  2 3  // all indices of 3

 

Explanation: 

Sorted array: 

Indices : 

Naive Approach

The idea is straightforward: sort the given array and start traversing the array. Check for every element. If the element is K, print its index else move to the next element.

Algorithm

  • Sort the given array using the sort function sort(a, a+n), where n is the size of the array.
  • Run a for loop for traversing the sorted array.
  • If the current element is K, print its index.

 

Implementation in C++

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

void print_all_indices(int a[], int n, int K)
{
    sort(a, a + n); // sorting the array

    for (int i = 0; i < n; i++) // traversing the array
    {
        if (a[i] == K)
            cout << i << " ";  // printing the index
    }
    
    cout << endl;
}


int main()
{
    int a[] = {2, 3, 6, 4, 3, 4, 0};

    int K = 3;

    int n = sizeof(a) / sizeof(a[0]);

    print_all_indices(a, n, K);
}

 

Output:

2 3

Complexity Analysis

Time complexity: We are using the sort function in the above approach, so the time complexity is O(n*logn), where n is the number of elements in the given array.

Space complexity: O(1) requires constant extra space.

Efficient Approach

We can improve the above solution by using the property of a sorted array, which states that if the array is sorted (ascending), the elements before the element with value K are smaller than K. The elements after the element with value K are greater than K.

Instead of sorting, we can use the above observation to find all indices of K in a sorted array.

If there are x elements smaller than K in the given array, the first index of K in the sorted array must be x (0-indexing). 

For all indices of K, we count the number of elements having value K and print the indices x, x+1, x+2, x+3 ……. and so on till (x+ count of K - 1).

Algorithm

  • Traverse the given array
  • Count the number of elements having a value less than K and store it in the count_smaller variable.
  • Count the number of elements having a value equal to K and store it in the count_k variable.
  • Run a for loop till count_k, print the count_smaller and keep incrementing the count_smaller variable.

 

For Example:

Input:  a[] = [ 3, 5, 7, 9, 7, 2, 7] , K = 7

 

Given array :

 

Initially count_smaller = 0, count_k = 0.

Step 1: a[0] = 3, count_smaller = 1, count_k = 0.

Step 2: a[1] = 5, count_smaller = 2, count_k = 0.

Step 3: a[2] = 7, count_smaller = 2, count_k = 1.

Step 4: a[3] = 9, count_smaller = 2, count_k = 1.

Step 5: a[4] = 7, count_smaller = 2, count_k = 2.

Step 6: a[5] = 2, count_smaller = 3, count_k = 2.

Step 7: a[6] = 7, count_smaller = 3, count_k = 3.

 

The indices are: count_smaller, count_smaller + 1, count_smaller + 2.

Indices = 3 4 5.

Implementation in C++

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

void print_all_indices(int a[], int n, int K)
{
    int count_smaller = 0;
    int count_k = 0;
    for (int i = 0; i < n; i++)
    {
        if (a[i] < K)
            count_smaller++;
        if (a[i] == K)
            count_k++;
    }

    for (int i = 0; i < count_k; i++)
    {
        cout << count_smaller << " ";
        count_smaller++;
    }
}

int main()
{
    int a[] = {3, 5, 7, 9, 7, 2, 7};

    int K = 7;

    int n = sizeof(a) / sizeof(a[0]);

    print_all_indices(a, n, K);
    
    return 0;
}

 

Output:

3 4 5

Complexity Analysis

Time complexity: We are traversing the given array, so the time complexity is O(n), where n is the number of elements in the given array.

Space complexity: O(1) requires constant extra space.

Frequently asked questions

Q1. Which sorting method is the most appropriate for an array?

Ans: Insertion sort can be preferred when the array is almost sorted. Merge sort is preferred when the order of the input is unknown because it has a worst-case time complexity of n*logn and is also stable.

 

Q2. Where does quicksort come into play?

Ans: The sorting algorithm is used to find information, and because Quicksort is the fastest algorithm, it is widely used as a more efficient method of searching. It's used wherever a stable sort isn't required. Only traverses the arrayQuicksort has a good locality of reference when used for arrays, making it a cache-friendly algorithm.

 

Q3. Which sorting algorithm is best for large data?

Ans: Insertion sort is the fastest for large numbers of data sets. This is a rare occurrence in practical sorting. It's worth noting that randomised Quicksort reduces the likelihood of worst-case scenarios, which is the case for in-order data if the pivot point in Quicksort is set to the first element.

Key Takeaways

This article discussed the naive approach and an efficient approach using the property of a sorted array for finding all indices of a given element in the sorted form of the given array with examples and its C++ code.

If you are a beginner, interested in coding and want to learn DSA, you can look for our guided path for DSA, which is free! 

Thank you for reading!

Was this article helpful ?
1 upvote

Comments

No comments yet

Be the first to share what you think