Searching

Lesson 20 of 23 in Coddy's C++ - Standard Template Library course.

Searching is the process of locating a particular element position in a sequence of elements.

A search algorithm is an algorithm that is given an argument x and tries to find an element whose value is x in a given set of values. So, it's possible the search for an elements of that value to be unsuccessful if that elements does not exist.

There are number of searching techniques and methods, but in C++ you will learn about:

Linear Search
Binary Search

Linear Search

Linear Search is the most basic searching technique and it is also easy to implement in C++. In the linear search as you can tell by the name, the key that's suppose to be searched is compared linearly with every element of the data sequence until it's found or the sequence ends.

Linear Search(sequence, key)
	for each item in sequence:
		if item == key
			return item's index

In real code, the linear search will look something like this:

int linear_search(int array[], int n, int x)
{
	for(int i = 0; i < n; i++)
		if(array[i] == x)
			return i;
	return 0;
}

int main()
{
	int array[] = {1, 2, 3, 4, 5};
	int n = 5;
	int x = 3;
	
	cout << "The index of the element " << x << " is " << linear_search(array, n, x);

Output:
The index of the element 3 is 2

As you can see from the code above, the linear search function is basically looping through the sequence of elements until it finds a match, if it doesn't find a match, it returns -1.

Binary Search

Binary Search is a searching algorithms for finding an element's position, but the array must be sorted.
The binary search algorithm uses the "divide and conquer" technique to search for the key. The list of elements is repeatedly divided into half and the element is searched for in the closer half.

Let's say we are searching for the element x = 4

So this is what the code will look like for the binary search.

int binarySearch(int array[], int x, int left, int right) {
  
  while (left <= right) {
    int mid = left + (right - left) / 2;

    if (array[mid] == x)
      return mid;

    if (array[mid] < x)
      left = mid + 1;

    else
      right  = mid - 1;
  }

  return -1;
}

int main()
{
    int array[] = {1, 5, 8, 10, 20};
    int x = 10;
    int n = 5;
    int result = binarySearch(array, x, 0, n - 1);
    
    if(result == -1)
    	cout << "Not found.";
    else
    	cout << "The element is found at " << result;

Output:
The element is found at 3

Remember what searching is, what it's purpose is and what we used it for. How we implement the linear search and how we implement the binary search. Keep practicing the advanced techniques in C++ through exercises.

Challenge

Medium

You are given 10 numbers from input. In the next line there is a number N. In the third line there are N numbers that represent what elements' positions you need to output to the screen.

Input
10 20 30 40 50 60 70 80 90 100
3
20
50
80

Output
1 4 7

Try it yourself

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

// Enter your code here

int main()
{
    // Enter your code here

    return 0;
}