Binary Search | DSA in C++ - Software Development PDF Download

Introduction

Binary search is a fundamental searching algorithm used to efficiently find a target value in a sorted array or list. It follows the principle of divide and conquer to quickly narrow down the search space. In this article, we will explore binary search in detail, including its implementation in C++ along with examples and explanations.

Prerequisites

Before diving into binary search, make sure you have a basic understanding of C++ programming and arrays. Familiarity with loops and conditional statements will also be helpful.

Binary Search Algorithm

Binary search is based on the following steps:

• Consider an array or list with elements sorted in ascending order.
• Start with the entire array.
• Compare the middle element of the array with the target value.
• If the middle element is equal to the target value, the search is successful.
• If the middle element is greater than the target value, repeat the search on the left half of the array.
• If the middle element is less than the target value, repeat the search on the right half of the array.
• Repeat steps 3 to 6 until the target value is found or the search space is exhausted.

Binary Search Implementation in C++

Let's now look at the implementation of binary search in C++. We will start with a basic iterative approach and then explore a recursive implementation.

Iterative Binary Search

#include <iostream>

using namespace std;

int binarySearch(int arr[], int size, int target) {

    int left = 0;

    int right = size - 1;

    while (left <= right) {

        int mid = left + (right - left) / 2;

        if (arr[mid] == target)

            return mid;

        if (arr[mid] < target)

            left = mid + 1;

        else

            right = mid - 1;

    }

        return -1; // Target value not found

}

int main() {

    int arr[] = {1, 3, 5, 7, 9};

    int size = sizeof(arr) / sizeof(arr[0]);

    int target = 5;

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

    if (result == -1)

        cout << "Element not found";

    else

        cout << "Element found at index: " << result;

    return 0;

}

Output:

Element found at index: 2

Explanation:

• We define a function 'binarySearch' that takes an array, its size, and the target value as parameters.
• Initially, we set the left pointer to the start of the array ('0') and the right pointer to the end of the array ('size - 1').
• Inside the 'while' loop, we calculate the middle index using the formula 'mid = left + (right - left) / 2'.
• We compare the middle element with the target value. If they are equal, we return the index.
• If the middle element is less than the target value, we update the left pointer to 'mid + 1' to search in the right half of the array.
• If the middle element is greater than the target value, we update the right pointer to 'mid - 1' to search in the left half of the array.
• The loop continues until the target value is found or the search space is exhausted. If the target value is not found, we return '-1' to indicate the failure of the search.

Recursive Binary Search

#include <iostream>

using namespace std;

int binarySearchRecursive(int arr[], int left, int right, int target) {

    if (left <= right) {

        int mid = left + (right - left) / 2;

        if (arr[mid] == target)

            return mid;

        if (arr[mid] < target)

            return binarySearchRecursive(arr, mid + 1, right, target);

        else

    return binarySearchRecursive(arr, left, mid - 1, target);

    }

    return -1; // Target value not found

}

int main() {

    int arr[] = {1, 3, 5, 7, 9};

    int size = sizeof(arr) / sizeof(arr[0]);

    int target = 5;

    int result = binarySearchRecursive(arr, 0, size - 1, target);

    if (result == -1)

        cout << "Element not found";

    else

        cout << "Element found at index: " << result;

    return 0;

}

Output:

Element found at index: 2

Explanation:

• The recursive implementation of binary search uses a helper function 'binarySearchRecursive' that takes additional parameters: 'left' and 'right' to specify the search space.
• Inside the function, we check if 'left <= right' to ensure the search space is valid.
• We calculate the middle index using the formula 'mid = left + (right - left) / 2' and compare the middle element with the target value.
• If the middle element is equal to the target value, we return the index.
• If the middle element is less than the target value, we make a recursive call with the updated left pointer ('mid + 1').
• If the middle element is greater than the target value, we make a recursive call with the updated right pointer ('mid - 1').
• The recursion continues until the target value is found or the search space is exhausted. If the target value is not found, we return '-1'.

Sample Problems

Problem 1: Given a sorted array '[2, 4, 6, 8, 10, 12]', find the index of the target element '6'.

Applying binary search, the target element '6' is found at index '2'.

Problem 2: Given a sorted array '[-2, 0, 3, 5, 7, 9]', find the index of the target element '0'.

Applying binary search, the target element '0' is found at index '1'.

Problem 3: Given a sorted array '[1, 3, 5, 7, 9]', find the index of the target element '4'.

Applying binary search, the target element '4' is not found in the array. The search returns '-1'.

Conclusion

Binary search is a powerful algorithm for efficiently searching sorted arrays or lists. It follows a divide and conquer approach, reducing the search space in half at each step. In this article, we explored binary search and its implementation in C++. We discussed both iterative and recursive approaches, along with example codes and explanations. By understanding the binary search algorithm, you can optimize your search operations and improve the efficiency of your programs.