Skip to content
CodeBreakdown

Search Algorithm

Searching is the process of finding a specific element in a collection of elements. There are many search algorithms available, each with its own advantages and disadvantages. In this section, we will discuss some of the common search algorithms in C++.

Linear search is a simple search algorithm that sequentially checks each element in a collection until a match is found or the whole collection has been searched. It is also known as a sequential search.

Here is an example of implementing linear search in C++:

main.cpp
#include <iostream>


using namespace std;


int linearSearch(int numbers[], int count, int key) {
    for (int i = 0; i < count; i++) {
        if (numbers[i] == key) {
            return i;
        }
    }


    return -1;
}


int main() {
    int numbers[] = {64, 34, 25, 12, 22, 11, 90};
    int count = sizeof(numbers) / sizeof(numbers[0]);
    int key = 22;


    int index = linearSearch(numbers, count, key);


    if (index != -1) {
        cout << "Element found at index: " << index << endl;
    } else {
        cout << "Element not found" << endl;
    }


    return 0;
}

The output of the program will be:

Terminal window
Element found at index: 4

Here is a GIF that demonstrates how linear search works:

Linear Search

Binary search is a more efficient search algorithm that works on sorted collections. It repeatedly divides the collection in half and compares the target value to the middle element of the collection. If the target value matches the middle element, the search is successful. If the target value is less than the middle element, the search continues on the lower half of the collection. If the target value is greater than the middle element, the search continues on the upper half of the collection.

Here is an example of implementing binary search in C++:

main.cpp
#include <iostream>


using namespace std;


int binarySearch(int numbers[], int low, int high, int key) {
    if (low <= high) {
        int mid = low + (high - low) / 2;


        if (numbers[mid] == key) {
            return mid;
        } else if (numbers[mid] > key) {
            return binarySearch(numbers, low, mid - 1, key);
        } else {
            return binarySearch(numbers, mid + 1, high, key);
        }
    }


    return -1;
}


int main() {
    int numbers[] = {11, 12, 22, 25, 34, 64, 90};
    int count = sizeof(numbers) / sizeof(numbers[0]);
    int key = 22;


    int index = binarySearch(numbers, 0, count - 1, key);


    if (index != -1) {
        cout << "Element found at index: " << index << endl;
    } else {
        cout << "Element not found" << endl;
    }


    return 0;
}

The output of the program will be:

Terminal window
Element found at index: 2

Here is a GIF that demonstrates how binary search works:

Binary Search