C++ Binary Search Using Dynamic Array

Introduction

Binary search is a search method that finds an element's index position in a sorted array. In C++, we can perform a binary search using two approaches - iterative and recursive. In this lab, we will perform a binary search operation using a dynamic array.

Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL cpp(("`C++`")) -.-> cpp/BasicsGroup(["`Basics`"]) cpp(("`C++`")) -.-> cpp/ControlFlowGroup(["`Control Flow`"]) cpp(("`C++`")) -.-> cpp/FunctionsGroup(["`Functions`"]) cpp/BasicsGroup -.-> cpp/variables("`Variables`") cpp/BasicsGroup -.-> cpp/data_types("`Data Types`") cpp/BasicsGroup -.-> cpp/operators("`Operators`") cpp/ControlFlowGroup -.-> cpp/conditions("`Conditions`") cpp/ControlFlowGroup -.-> cpp/while_loop("`While Loop`") cpp/FunctionsGroup -.-> cpp/function_parameters("`Function Parameters`") subgraph Lab Skills cpp/variables -.-> lab-96172{{"`CPP Binary Search Using Dynamic Array`"}} cpp/data_types -.-> lab-96172{{"`CPP Binary Search Using Dynamic Array`"}} cpp/operators -.-> lab-96172{{"`CPP Binary Search Using Dynamic Array`"}} cpp/conditions -.-> lab-96172{{"`CPP Binary Search Using Dynamic Array`"}} cpp/while_loop -.-> lab-96172{{"`CPP Binary Search Using Dynamic Array`"}} cpp/function_parameters -.-> lab-96172{{"`CPP Binary Search Using Dynamic Array`"}} end

Create a new C++ file

First, we create a new C++ file in the ~/project directory named main.cpp.

touch ~/project/main.cpp

Next, we include the necessary header files - iostream, algorithm, and vector.

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

using namespace std;

Create a dynamic array and populate it with elements

We create a dynamic array of integers by using the vector class and populate it with sorted integers.

vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};

Implement binary search function

Next, we implement the binary search function that searches for an element's index position in a sorted array using the iterative approach.

int binarySearch(vector<int> arr, int target) {
    int low = 0;
    int high = arr.size() - 1;
    int mid;

    while (low <= high) {
        mid = (low + high) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return -1;
}

Call binary search function and output the result

Finally, we call the binary search function with an element to search for and output the result to the console.

int target = 7;
int result = binarySearch(arr, target);

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

Compile and run the program

Compile and execute the program in the terminal by running the following command:

g++ main.cpp -o main && ./main

Final code

Here is the full code of the main.cpp file:

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

using namespace std;

int binarySearch(vector<int> arr, int target) {
    int low = 0;
    int high = arr.size() - 1;
    int mid;

    while (low <= high) {
        mid = (low + high) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return -1;
}

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};
    int target = 7;
    int result = binarySearch(arr, target);

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

    return 0;
}

Summary

In this lab, we learned how to perform binary search using a dynamic array in C++. We used the iterative approach and implemented a binary search function to search for an element's index position in a sorted array. We also learned how to create a dynamic array using the vector class in C++.

CPP Binary Search Using Dynamic Array