Understanding Binary Search

Understanding Binary Search
Understanding Binary Search

Introduction

Let’s learn today about an efficient Searching Algorithm, i.e., Binary Search. It is also known as half interval search, logarithmic search, and binary chop.  

It is a searching algorithm that helps find the element in the array and return the respective index. Additionally, we could also return a flag value to denote the element does not exist.

Binary Search follows the divide and conquer policy, i.e., searches an element by repeatedly dividing the array into two parts for every comparison. 


Note: It can only be applied on sorted arrays or the functions which are monotonic in nature.

So, we begin the search by defining two pointers – low and high. Low points to index 0 and high points to arr.length-1 index. Also, let the array be sorted in ascending order. Then we repeatedly find the middle element and compare it with the target element. Now three scenarios are possible: 

If middle element = target element => our search ends as the target element is found

If middle element > target element => we move towards left side

If middle element < target element => we move towards right side

So, here let’s say we have to search element 50 in our given array. 

illustrative_diagram

We define our low pointer = 0, high pointer = 6 (index).

blog banner 1

Then we define a loop where we work till low < high. 

Then we find mid = (low+high)/2

Note: If the constraints (i.e., the array length is of order O(10^9), the above formula could result in overflow error, and hence then, we should use mid = (low + (high-low)/2). This would also give the same answer but prevent an overflow error.

Step 1: First, we find mid = (0+6)/2 = 3 => mid element = 45. Since 45 < 50(our target element) => we move towards the right by changing our low = mid+1.

Step 2: Now, we again find mid = (4+6)/2 = 5 => mid element = 71. Since 71 > 50(our target element) => we move towards left by changing our high = mid-1

Step 3: Now, we find mid = (4+5)/2 = 4 => mid element = 50. Since 50 = 50(our target element) => Our target element is found and hence we return true, or the respective index(i.e., 4 here) depending upon our question and breaks from the loop.

If we cannot find the target element in the given array, we would return -1(or any flag value) or false.

illustrative_diagram2

So, this particular searching algorithm is known as Binary Search as in each iteration, the array is further divided into two halves. 

Implementation in C++/Java/Python

Let’s have a look at its implementations in various languages –

C++

#include<iostream>
using namespace std;
int main() {
    // Enter Input array
    int n = 0;
    cout<<"Enter size of array: ";
    cin >> n;
    int arr[n];
    cout<<"Enter Numbers: ";
    for(int i = 0; i < n; i++)
        cin>>arr[i];
 
    // Input the target element
    cout<<"\nEnter a Number to Search: ";
    cin>>num;
 
    // Apply Binary Search
    int index = -1;  // -1 is the flag value
    int low = 0;
    int high = n-1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
  
        // Check if target element is present at mid
        if (arr[mid] == num)
            index = mid;
            break;
  
        // If num greater than arr[mid], ignore left half
        if (arr[mid] < num)
            low = mid + 1;
  
        // If num is smaller than arr[mid], ignore right half
        else
            high = mid - 1;
    }
 
    
    if (index == -1) cout << “\nElement not found”;
    else cout<<"\nFound at Index No."<< index;
    cout << endl;
    return 0;
}

Output:

Enter size of array: 10
Enter Numbers: 3 2 4 5 6 7 8 9 10 11
Enter a Number to Search: 5
Found at Index No. 3

Java

#import java.util.*;
 
public static void main(String[] args){
    Scanner s = new Scanner(System.in);  
    // Input size of array
    System.out.println("Enter size of array: ");
    int n = s.nextInt();  
 
    // Enter Input array
    System.out.println("Enter Numbers: ");
    for(int i=0; i<n; i++)
        arr[i] = s.next();
 
    // Input the target element
    System.out.println("Enter a Number to Search: ");
    int num = s.next();
 
    // Apply Binary Search
    int index = -1;  // -1 is the flag value
    int low = 0;
    int high = n-1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
  
        // Check if target element is present at mid
        if (arr[mid] == num)
            index = mid;
            break;
  
        // If num is greater than arr[mid], ignore left half
        if (arr[mid] < num)
            low = mid + 1;
  
        // If num is smaller that arr[mid], ignore right half
        else
            high = mid - 1;
    }
  
 
    if (index == -1) System.out.println(“Element not found”);
    else 
         System.out.println("Found the target element at Index No."+ index);
}

Output:

Enter size of array: 10
Enter Numbers: 3 2 4 5 6 7 8 9 10 11
Enter a Number to Search: 5
Found at Index No. 3

Python

// Perform Binary Search
def binarySearch(arr, low, high, x):
  
    while low <= high:
  
        mid = low + (high - l) // 2;
          
        # Check if num is present at mid
        if arr[mid] == num:
            return mid
  
        # If num is greater than arr[mid], ignore left half
        elif arr[mid] < num:
            low = mid + 1
  
        # If num is smaller than arr[mid], ignore right half
        else:
            high = mid - 1
      
    # element not present
    return -1
  
# Driver Code
arr = [ 2, 3, 4, 10, 40 ]
num = 10
  
# Function call
result = binarySearch(arr, 0, len(arr)-1, num)
  
if result != -1:
    print ("Element is present at index % d" % result)
else:
    print ("Element is not present in array")

Output:

Element is present at index 3

Time and Space Complexity

Time Complexity

Best Time Complexity: O(1) as if the element is present at the middle index, only one comparison is required.

Average Time Complexity: It is the average of time complexities to find the element at every index. So, since the array gets divided into half in every iteration, it follows:

n -> n/2 -> n/4 -> n/8….. n/(2^k)

So, follows an Recurrence Relation : T(n) = T(n/2) + c (where c is constant)

This relation could be solved using a Recurrence Tree or Master Method, hence giving a complexity of O(log n (base 2)).

Worst Time Complexity: O(logn (base 2)) due to the recurrence relation.

Space Complexity: O(1) as we aren’t utilizing or creating any space apart from the given array length as an input.

where n is no of elements in an array

Advantages and Applications of Binary Search

  1. It’s extremely simple to understand both concepts wise and implementation wise.
  2. Although it requires a sorted array, it is extremely useful to efficiently search an element in long lists as it breaks down the entire collection into half in every iteration.
  3. When the target element matches the middle element of the array, the searching work is done in O(1).

Linear Search VS Binary Search

Linear SearchBinary Search
It uses an iterative or sequential approach.It uses a divide and conquer approach.
It does not depend on the arrangement of elements in an array.It requires a sorted arrangement of elements (either ascending or descending).
Worst-case time complexity of the linear Search is O(N)Worst-case time complexity of the  binary Search is O(log2N).
It sequentially access the elementsIt accesses the data randomly
It performs equality comparisonsit performs ordering comparisons
Best Case is when an element is found at 1st position.Best Case is when an element is found at the middle position.
Less ComplexMore Complex
Less efficientMore efficient

Frequently Asked Questions

What is Binary Search? Explain.

In Computer Science, Binary Search is a method for finding a target element in a sorted array by repeatedly dividing the search interval in half.

What are the types of searching?

There are various types of searching algorithms like jump search, binary Search, interpolation search, fibonacci Search etc.

Why is it called Binary Search?

It is called Binary Search as it follows a divide and conquer approach by repeatedly splitting the search space in 2 halfs. Hence, It is also called Dichotomic Search (literally: “that cuts in two”)

Which is faster, binary or linear Search?

Binary Search is faster than Linear Search as The worst-case time complexity of the linear Search is O(N) while Binary Search has O(log2N). But Binary search can only be applied if the array is sorted. However, there is no such condition for Linear Search.

Key Takeaways

In this blog, we learned how to apply Binary Search on the given array. 

  • It is also known as half interval search, logarithmic Search and binary chop.  
  • In it, we split the search interval in half in every interval following the divide and conquer approach, reducing the target element’s search space.  
  • It works for sorted arrays only.
  • Its Best Case Time Complexity is O(1), but Worst Case Time Complexity is O(logn), where n is the number of elements in an array.

Check out more blogs on Linear Search to read more about these topics in detail. And if you liked this blog, share it with your friends!

By: Raksha Jain