Binary Search

Divide and Conquer to Efficiently Find Target in Sorted Data

Introduction

Binary Search is a fast searching algorithm to find the position of a target value in a sorted array. It repeatedly splits the array in half checking if the target is smaller or larger than the middle value.If the target is smaller than the middle value, it searches the left half, if larger it searches the right half. The search continues in the left or right half until the target is found or no more elements are left to check.

How Binary Search Works?

1

Find the middle

Look at the middle element of the sorted list.

2

Compare the target

  • If the middle element is the target, the searching is terminated.
  • If the target is smaller, search on the left half.
  • If the target is bigger, search on the right half.
3

Repeat

Repeat the process until the target is found or the total search is finished.

Carousel image 1
Carousel image 2
Carousel image 3
Carousel image 4

Iterative Approach

//binarysearch.cpp
#include<iostream>
#include<vector>
using namespace std;
int binarySearch(vector<int>& arr, int target){
int firstIndex = 0;
int lastIndex = arr.size() - 1;
while(firstIndex <= lastIndex){
    int mid = firstIndex + (lastIndex - firstIndex) / 2;
    if(arr[mid] == target) return mid;
    else if(arr[mid] < target){
        firstIndex = mid + 1;
    }                                       
    else{
        lastIndex = mid - 1;
    }
}
return -1;
}
int main(){
vector<int> arr{3, 5, 7, 11, 12, 15, 16};
int target = 7;
int idx=binarySearch(arr, target);
if(idx!=-1)
cout << "The "<<target<<" is present at index: "<<idx;
else
cout<<"Not Present";
return 0;
}

Recursive Approach

//binarysearch.cpp
#include <iostream>
#include <vector>
using namespace std;
int recursionBinarySearch(vector<int> &arr, int l, int r, int target)
{
if (l > r)
    return -1;
int mid = (l + (r - l) / 2);
if (arr[mid] == target)
    return mid;
if (arr[mid] > target)
    return recursionBinarySearch(arr, l, mid - 1, target);
return recursionBinarySearch(arr, mid + 1, r, target);
}
int main()
{
vector<int> arr{3, 5, 7, 11, 12, 15, 16};
int target = 3;
int idx = recursionBinarySearch(arr, 0, arr.size() - 1, target);
if (idx != -1)
    cout << "The " << target << " is present at index: " << idx;
else
    cout << "Not Present";
return 0;
}

Time Complexity

Best CaseO(1):The best case occurs when the target is found at the middle of the array on the first search.

Worst CaseO(log n):In the worst case, the search space is halved at each step, leading to a logarithmic number of comparisons. So, for n elements it takes approximately log₂(n) steps to find the target or determine that it doesn't exist.

Space Complexity

Space ComplexityO(1):The Space Complexity is constant because Binary Search only requires a fixed amount of space (for variables like firstIndex, lastIndex, and mid) regardless of the size of the input array. It doesn't require any extra space proportional to the input size.

AspectLinear SearchBinary Search
Time ComplexityWorst-case: O(n).Worst-case: O(log n).
Space ComplexityO(1) (constant space).O(1) (constant space).
EfficiencyLess efficient for large datasets.More efficient for large datasets.
ImplementationSimple, iterate through all elements.Uses divide-and-conquer.
Use CasesSmall or unsorted arrays.Large sorted arrays.
Array RequirementCan be used on unsorted arrays.Requires sorted arrays.