C++ Program To Binary Search Using Dynamic Array

A binary search is a method of locating a certain element in a list. In this tutorial, we will perform a binary search operation to discover an element's index position in a list with two different methods.

Binary Search - A basic Introduction

Binary search is the most popular program for searching. Let's say we have a thousand-element list and we need to get the index position of a specific entry. Using the binary search technique, we may quickly determine the index location of an element. To use the binary search method, the entries in the list must be sorted. If the components aren't already sorted, sort them first. To execute binary search we can follow two approaches which are discussed below:

1. Iterative Method

2. Recursive Method

We will discuss all these approaches in detail separately.

Approach 1: Iterative Binary Searching Operation

In this method, we'll iterate through the entire list, repeating a series of instructions. We'll keep looking for the middle value until we've found it. Let's have a look at the Algorithm followed by code for better understanding:

Binary Search Algorithm

1. Create a function binary_search() which accepts 4 parameters(array, low, high, a).
2. Declare two variables to store the highest and the lowest values in the list.
3. Then Follow step 4 until the lowest and highest meet each other:
4. mid = (low + high)/2 if (a == arr[mid]) return mid else if (a > arr[mid]) // a is on the right side low = mid + 1 else // a is on the left side high = mid - 1
5. Initialize the array and the element to be found
6. Print the resulting position if the element is found else print Not found.

C++ Program of Binary Search

As discussed above in the algorithm, let us now dive into the programming part of the iterative binary search operation influenced by the algorithm.

// Binary Search in C++

#include <iostream>
using namespace std;

int binarySearch(int array[], int x, int low, int high) {
  
	// Repeat until the pointers low and high meet each other
  while (low <= high) {
    int mid = low + (high - low) / 2;

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

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

    else
      high = mid - 1;
  }

  return -1;
}

int main(void) {
  int array[] = {3, 4, 5, 6, 7, 8, 9};
  int x = 4;
  int n = sizeof(array) / sizeof(array[0]);
  int result = binarySearch(array, x, 0, n - 1);
  if (result == -1)
    printf("Not found");
  else
    printf("Element is found at index %d", result);
}

Element is found at index 1

Approach 2: Recursive Binary Search Operation

In the binary search, the recursion approach can be used. We'll create a recursive function that keeps calling itself until the condition is met. The recursive approach follows the divide and conquer method which is a method of resolving a complex issue by dividing it down into smaller sub-problems, solving them, and then combining them to get the desired result. Let's have a look at the Algorithm followed by code for better understanding:

Algorithm

1. Create a function binary_search() which accepts 4 parameters(array, low, high, a).
2. Then Follow step 3 until the lowest and highest meet each other:
3. mid = (low + high) / 2 if a == arr[mid] return mid else if a > arr[mid] // a is on the right return binary_eearch(arr, a, mid + 1, high) else // a is on the right return binary_search(arr, a, low, mid - 1)
4. ze the array and the element to be found
5. Print the resulting position if the element is found else print Not found.

C++ Program of Binary Search

As discussed above in the algorithm let us now dive into the programming part of recursive binary search operation influenced by the algorithm.

// Binary Search in C++

#include <iostream>
using namespace std;

int binarySearch(int array[], int x, int low, int high) {
  if (high >= low) {
    int mid = low + (high - low) / 2;

    // If found at mid, then return it
    if (array[mid] == x)
      return mid;

    // Search the left half
    if (array[mid] > x)
      return binarySearch(array, x, low, mid - 1);

    // Search the right half
    return binarySearch(array, x, mid + 1, high);
  }

  return -1;
}

int main(void) {
  int array[] = {3, 4, 5, 6, 7, 8, 9};
  int x = 4;
  int n = sizeof(array) / sizeof(array[0]);
  int result = binarySearch(array, x, 0, n - 1);
  if (result == -1)
    printf("Not found");
  else
    printf("Element is found at index %d", result);
}

Element is found at index 1

Conclusion

In this tutorial, we have seen two approaches to the binary search operation. The first approach is the iterative approach which is direct because in this method we'll keep looking for the middle value until we've found it. The second approach is a recursive method in which we'll create a recursive function that keeps calling itself until the condition is met.