Binary Search

Binary Search is a searching algorithm to find an element from a Sorted Array. This type of search is also known as half-interval search or logarithmic search. Binary Search like Linear Search applies to Linear Data Structures like Arrays and Hash Tables. Binary Search is one of the best performing search algorithm for Linear Data Structures and has many practical use cases.

Time complexity of Binary Search is O_{(log n)} and space complexity is O₍₁₎. This is a logarithmic search algorithm and Time complexity line is always well below the Linear Time Complexity line. That means, Binary Search performance increases as the number of inputs increases, making this suitable for larger data collections.

Binary Search Uses

Binary search can be used to find solutions for a wider range of problems. Some of the use cases are listed below.
1. Used mainly for use cases that manages huge amount of data and faster search is of the primary importance above insert update and delete operations, like in a dictionary.
2. Finding the next-smallest or next-largest element in the array relative to a target element.
3. Numerical solutions to an equation.
4. Can be used to access ordered data quickly when memory space is tight.
How Binary Search Works

Binary Search is a divide and conquer method, that has higher efficiency for larger sets of data. Binary Search should be performed on a sorted array, whereas in Linear Search, array can be in any order.

This algorithm basically compares the search element with the middle element of the remaining array. Then checks if it is greater or lesser or equal and eliminating the other half for each iteration, till the result is obtained. Binary search is a well performing algorithm and has many practical applications.

Check the below gif image to easily understand the search process.

As you can see, Binary Search require the data to be kept sorted and this may be an additional overhead for insert, update or delete operations.
Algorithm

Binary Search Algorithm flow is listed as below.

Input : A sorted list of elements.
Output : Element position, if found. Else not found message.
1. Start.
2. Set start = 0, end = length of array, pos = -1.
3. Check start <= end, if true go to next step, else go to step 8.
4. Find middle node.
5. If middle node value = searched value, element found. Go to step 8.
6. Else if middle node value < searched value, set start = middle node + 1. Go to step 4.
7. Else, end = middle node - 1. Go to step 4.
8. If pos > -1, element found. Display result.
9. Else if pos = -1, element not found. Display not found message.
10. Stop.

Code Samples

Below are few sample code implementations of Binary Search Algorithm in Python, Java, C# and JavaScript.

arry = [10, 12, 15, 19, 22, 25, 28, 30, 35, 40]

find = 35
pos = -1
count = 0

start = 0
end = len(arry) - 1

while start <= end:
    midNode = (start + end) // 2
    count += 1

    if arry[midNode] == find:
        pos = midNode
        break
    
    if arry[midNode] < find:
        start = midNode + 1
    else:
        end = midNode - 1

if(pos > -1):
    print("Element found at position : ", pos)
    print("Number of Iterations : ", count)
else:
    print("Element not found")
    print("Number of Iterations : ", count)

class BinarySearch   
{
    public static void main(String[] args)   
    {  
        int arry[] = {10, 12, 15, 19, 22, 25, 28, 30, 35, 40};
        int find = 35;
        int pos = -1;
        int count = 0;

        int start = 0;
        int end = arry.length - 1;

        while (start <= end) {
            int midNode = (start + end) / 2;
            count += 1;
        
            if (arry[midNode] == find){
                pos = midNode;
                break;
            }
            
            if (arry[midNode] < find)
                start = midNode + 1;
            else
                end = midNode - 1;
        }

        if(pos > -1) {
            System.out.println("Element found at position : " + pos);
            System.out.println("Number of Iterations : " + count);
        }
        else {
            System.out.println("Element not found");
            System.out.println("Number of Iterations : " + count);
        }
    }
}

using System;
using System.Threading;

namespace DSA
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] arry = { 10, 12, 15, 19, 22, 25, 28, 30, 35, 40 };
            int find = 35;
            int pos = -1;
            int count = 0;

            int start = 0;
            int end = arry.Length - 1;

            while (start <= end)
            {
                int midNode = (start + end) / 2;
                count += 1;

                if (arry[midNode] == find)
                {
                    pos = midNode;
                    break;
                }

                if (arry[midNode] < find)
                    start = midNode + 1;
                else
                    end = midNode - 1;
            }

            if (pos > -1)
            {
                Console.WriteLine("Element found at position : " + pos);
                Console.WriteLine("Number of Iterations : " + count);
            }
            else
            {
                Console.WriteLine("Element not found");
                Console.WriteLine("Number of Iterations : " + count);
            }
            Thread.Sleep(5000);
        }
    }
}

function binarySearch(find) {
    var arry = [ 10, 12, 15, 19, 22, 25, 28, 30, 35, 40 ];
    var pos = -1;
    var count = 0;

    var start = 0;
    var end = arry.length - 1;

    while (start <= end)
    {
        var midNode = Math.floor((start + end) / 2);
        count += 1;

        if (arry[midNode] == find)
        {
            pos = midNode;
            break;
        }

        if (arry[midNode] < find)
            start = midNode + 1;
        else
            end = midNode - 1;
    }

    if (pos > -1)
    {
        alert("Element found at position : " + pos);
        alert("Number of Iterations : " + count);
    }
    else
    {
        alert("Element not found");
        alert("Number of Iterations : " + count);
    }
    return false;
}

var find = 35;
binarySearch(find);

Binary Search

Binary Search Uses

How Binary Search Works

Algorithm

Code Samples