Problem Solving: Brute Force Searching I

Learn about the brute force searching technique by finding the first and kth occurrence of an element in an array.

We'll cover the following

Search problems

In this lesson, we will learn to solve multiple search problems 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.

Playground for your implementation

Please write your code in the given playground.

6 2 4 6 8 10 1 3 -1
Add the complete code

Loading the data

Task 0: Load the data and display it.

First, we will write the function loadData(), which reads the number stream (ending with -1) from the file (“Data.txt”). We have three parameters in the loadData() function:

  • D[]: This is the array to read numbers.
  • &size: This counts the number of elements in an array.
  • capacity: This is to determine the maximum limit of numbers that can be loaded in D[].
void loadData(int D[], int &size, int capacity)

Also, we will write the printing function:

void printData(int D[], int size)

Try writing the load function. You may refer to the following if you have any confusion:

Press + to interact
void loadData(int D[ ], int &size, int capacity)
{
    ifstream Rdr("Data.txt");  
    size = 0;   // assign size to 0
    for(int di = 0; Rdr && di < capacity ; di++)
    {
        int val;
        Rdr>>val; // Read the number from file
        if(Rdr && val!=-1) // if Rdr was able to read if(Rdr) will be true; 
        {                  // other false
            D[di] = val;   // place the val on D[di] index
            size++;        // size should be increased.
        }
        else
        {
            break;   // if the Rdr was not able to read or delimiter -1 was read
        }
    }
}
  • Line 5: The for loop will execute until the file descriptor Rdr reaches the end of the file or the capacity of the array becomes full.
  • Line 9: The if(Rdr) condition checks if Rdr is not at the end of the file, while the val!=-1 condition ensures that val is not equal to -1.
  • Lines 11–12: These lines will be executed and will assign val an array at index D[di] and increment it in size.
  • Line 16: Otherwise, the loop should break.

loadData()

Question

What if we do not set size = 0 in line 4?

Show Answer

Search the first occurrence

Task: Find the first index of a specific element in an array.

Sample output

        Program: Searching problems

Data: { 2 4 6 8 10 6 1 3 }


------------------------------------------

Searching the first Occurence of: 6
6 is found at index :2

Idea:

  • We will iterate through the entire data array D, from index D[0] to D[size-1]. If the indexed element is the target element, we’ll return that index. Otherwise, we’ll keep traversing the array.
  • If the traversal is complete and we were not able to find the element, we’ll return -1, which shows that the targeted element is not found.

Look at the animation below:

Here is a wrong implementation of findFirst. Can you figure out the bug?

Press + to interact
int findFirst(int D[ ], int size, int t)
{
    for(int i=0; i<size; i++)
    {
        if(D[i]==t)
            return i;
        else
            return -1;
    }  
}

Instruction: Write the code in the exercise playground, and debug the code to figure out the bug.

Direction: Search the value 6. Although it is present inside the array, our code is displaying otherwise. Can you find the error? We recommend that you execute the program, see how the instructions are executing, especially the searching loop, and resolve the bug.

Search the kth occurrence

Task: Find the index of the kth occurrence of an element in an array.

Sample input

        Program: Searching problems

Data: { 2 4 6 8 10 6 1  6 3 }


------------------------------------------

Searching the Kth Occurrence of: 6
K: 2
6 is found at: 5

Let’s implement the following function:

void findKthIndex(int D[ ], int size, int k, int t)

Idea:

  • Iterate through the array.
  • In each iteration, we will check whether the target element t is present in the array or not.
    • We will maintain the number of occurrences in the count variable, and on every find, we will increment count by 1.
    • In the iteration, when we find the kth occurrence, i.e., count==k, we will return that index i.
  • If the loop ends, that means the kth occurrence does not exist. In such a case, it will return -1.

Look at the animation below:

Let's look at the implementation of this.

Press + to interact
int findKthIndex(int D[ ], int Size, int k, int t)
{
    int count=0;
    for(int i=0; i<Size; i++)
    {
        if(D[i]==t)      // value t is found
        {
            count++;     // increment the count, to remember the occurrence #
            if(count==k) // if the occurrence number is equal to k
                return i;// return the current found index
        }
    }
    return -1;           // When kth occcurrence does not exists
}

Instruction: Write the above code in the exercise playground and test it by uncommenting the main() lines.