Problem Solving: Brute Force Searching III

Learn how to use the brute force searching technique to find all the occurrences of an element in an array.

We'll cover the following

Search problems

In this lesson, we will learn to solve a search problem using arrays. Write your code in the playground here. We have provided you the main() function and all the required prototypes of the functions. Uncomment the code lines in the main() function after each task is done, and test whether your program is working correctly or not.

Exercise playground

Please write your code in the given playground.

2 3 4 1 2 1  5 -1
Exercise playground with all the function prototypes

Searching all the occurrences

Task: Find all the indices of an element in an array.

Sample input

Data: { 2 3 4 1 2 1 5 }
Press + to interact
      Program: Searching problems
Data: { 2 3 4 1 2 1 5 }
------------------------------------------
Searching all the Occurence of: 2
2 is found at { 0 4 }

Let’s implement a function findAllIndices().

void findAllIndices(int D[ ], int size, int t, int Is[], int &sizeIs)
  • To find the target element t, we pass D[] and size because we need to perform the search on the data present in the array D[], while size shows the number of elements present in the array.
  • Is[] is the array in which the function will write all the indices where the occurrences of the target element are found, and sizeIs shows the count of found occurrences, i.e., how many times the value is found.

Idea:

  • We will first initialize sizeIs to 0, as we need to update the garbage value inside the variable.
  • We will iterate through each element present in D[].
    • We’ll check if D[i] == t. Then we will save this index i inside the indices array at Is[sizeIs] = i.
    • Along with that, we’ll increment sizeIs so that now the next index found should be stored at the next memory location.
    • With sizeIs, we keep track of how often the target element t is found inside the data D[].
Press + to interact
void findAllIndices(int D[ ], int size, int t, int Is[], int &sizeIs)
{
    sizeIs = 0;
    
    for(int i=0; i<size; i++)
    {
        if(D[i]==t)
        {
            Is[sizeIs] = i;
            sizeIs++;
        }
    }
}

Instruction: Write the code in the exercise playground and test it.

Quiz

1

What is the function going to return?

int f1(int D[], int size, int t)
{
   int fi = -1;
   for(int i=0; i<size; i++)
   {
      if(D[i]==t)
       fi = i;
   }
   return fi;
}
int main()
{
   int D[] = {1,2,3,2,3,1}, size = 6, t=3;
   cout << f1(D, size, t);
   return 0;
}
A)

The first occurrence of t in the data D[ ].

B)

The last occurrence of t in the data D[ ].

C)

It will always return -1.

Question 1 of 30 attempted