Binary Search

Overview

• What is Binary Search?
• Why use Binary Search?
• How to implement Binary Search?
• Sample code for better understanding.
• Code explaination.

Introduction

Binary search is one of the fundamental algorithms used in Computer Science. It is used to effeciently find an element in a sorted list , minimizing the nummber of comparisons needed.
Unlike linear search (which checks each element suquentially), binary search divide the array in halves to find the target more quickly.

How to Implement

1. Start with the Middle element: Given a sorted array, start by comparing the target value with the middle element of array.

2. Halve the Search Space:

• If the target value is equal to the middle element , the target value have been found.
• If the target value is less than the middle element, repeat the process on the left sub-array (from start to mid-1 index of current array).
• If the target value is greater than the middle element , repeat the process on right sub-array(from mid+1 to end index of current array).

3. Repeat until Found or Empty: Continue halving the search space until you either find the target or the search space is empty.

Why use binary search?

Binary search is incredibly efficient, reducing the time complexity to 𝑂(log𝑛) ,where 𝑛 is the number of elements in the array. This is much faster than linear search's 𝑂(𝑛) time complexity, especially for large datasets.
Always remember that Binary search is not a problem , it is a concept , which will help in solving many problems in easy and efficient way.

Example

Imagine you have a sorted array of numbers:
[1,3,5,7,9,11,13,15,17,19] , and you want to find the number 11.

Compare 11 with the middle element (which is 9).

Since 11 is greater than 9, look at the right half:
[11,13,15,17,19].

The new middle element is 15.

Since 11 is less than 15, look at the left half:
[11,13].

Now, the middle element is 13.

Since 11 is less than 13, look at the left half:
[11].

The middle element is now 11, which is the target value.

Code Implementation in C:

#include<stdio.h>

int binary_Search(int arr[], int low, int high, int sElement){
    
    while(low<=high){
        int mid = low + (high-low)/2;
        
        // Check if sElement is present at mid
        if (arr[mid] == sElement)
            return mid;
        
        // If sElement greater, ignore left half
        if (arr[mid] < sElement)
            low = mid + 1;

        // If sElement is smaller, ignore right half
        else
            high = mid - 1;
    }
    // if there is no such element found than
    return -1;
}

void main(){
  int n, arr[100], sElement, result;
  printf("Enter size of array: ");
  scanf("%d",&n);
  printf("Enter elements of array:\n");
  for(int i=0; i<n; i++){
      scanf("%d",&arr[i]);
  }
  printf("Enter element to be search: ");
  scanf("%d",&sElement);
  result = binary_Search(arr, 0, n-1, sElement);
  if(result == -1) 
     printf("Element is not present in array");
  else
     printf("Element is present at index %d",result);
}

Code Implementation in C++:

#include<bits/stdc++.h>
using namespace std;
bool binary_search(vector<int> &vec, int low,int high,int key){
    while(low<=high){
        int mid=(low+high)/2;
        if(vec[mid]==key)
        return true;
        if(vec[mid]>key)
        high=mid-1;
        else
        low=mid+1;
    }
    return false;
}
int main(){
    int n,key;
    cin>>n>>key;
    vector<int> vec(n);
    for(int i=0;i<n;i++)
    cin>>vec[i];
    sort(vec.begin(),vec.end());
    if(binary_search(vec,0,vec.size()-1,key))
    cout<<"found";
    else
    cout<<"not found";
}

About Code:

• Binary_search is a function with return type as boolean (0 or 1)
  that take vector ,starting index , ending index and target(key) value (that we have to find) as inputs.
• vector array is basically a dynamic array in c++ that can grow or shrink in size as needed ( will try to cover this as seperate concept).
• sort function and vec.size function , as the name suggests sort the vector and give the size of vector array respectively.(these will also be discussed with vector concept).