C++ Binary search

Introduction

Binary search is a search algorithm that finds the position of a target value within a sorted array.
It compares the target value to the middle element of the array.

Source: Tenor.com

Comparison with linear search:

	Binary search	Linear search
efficiency	Efficient for large lists	Efficient for small lists
Requirement	Requires sorted list	No need to sort
Average case for 10 records	3 comparisons	5 comparisons
Average case for 1000 records	10 comparisons	500 comparisons
Average case for 10000 records	14 comparisons	5000 comparisons

Implementation

Three indexes are used to implement binary search:

left: the leftmost index of the array
right: the rightmost index of the array
mid: the middle index of the array

In each iteration, the target value is compared with the middle element.
Case 1: If the target value is equal to the middle element, the search is successful.
Case 2: If the target value < the middle element, the right index is updated to mid - 1.
Case 3: If the target value > the middle element, the left index is updated to mid + 1.

Pseudocode

left = 1
right = n
mid = integral of (left + right) / 2
while left <= right and arr[mid] != target		// exit when target is found (Case 1)
  if target < arr[mid]					// target < middle (Case 2)
	right = mid - 1
  else							// target > middle (Case 3)
	left = mid + 1
  mid = integral of (left + right) / 2

Task

Complete the binary search in the following program:

#include <iostream>
using namespace std;
int main(){
  int arr[] = {13, 24, 35, 46, 57, 68, 79, 90, 101, 112};
  int n = 10, target, left, right, mid, flag = 0;
  left = 0;
  right = n - 1;
  mid = (left + right) / 2;

  cout << "Enter the target value: ";
  cin >> target;

  // binary search here



  // output result
  if (flag == 1)	
    cout << "Target value found at index " << mid << endl;
  else
	cout << "Target value not found" << endl;
}

Reference

GeeksforGeeks