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

**Recommended Problem - **__Merge K Sorted Arrays__

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!