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

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

Comments

## No comments yet

## Be the first to share what you think