Binary Search

Binary Search tries to find an element in a sorted array. It compares the middle element of the array with the searched element.
Thus we get the following cases,

Case 1 : If the middle element equals the searched element, the position of the middle element is returned.
Case 2 : If the middle element is bigger than the searched element, the left part of the array is searched using the same logic i.e binary search.
              Left part of the array : [ 0 … mid - 1 ]
Case 3 : If the middle element is smaller than the searched element, the right part of the array is searched using the same logic i.e binary search.
              Right part of the array : [ mid + 1 … end-1 ]


Algorithm : Binary Search

1. Binary Search ( Array, Search element N )
2.     Beg = 0, End = Sizeof ( Array ) - 1
3.     While (Beg <= End)
4.         Mid = Beg + ( End - Beg ) / 2
5.         If ( Array [ Mid ] == N )
6.             Return Mid as the index of the found element N.
7.         Else If ( Array [ Mid ] < N )
8.             Beg = Mid + 1.
9.         Else
10.            End = Mid - 1.
11.     Return -1 if the element that we are looking for i.e N is not found in the array.


Example of Binary Search Binary_Search_Image

Time complexity of Binary Search : Log(N)


Why is mid calculated as mid = beg + (end-beg)/2 ?

Integer range is -2,147,483,648 to 2,147,483,647. If you are searching in an array of size 2,000,000,000 and the element searched for is located at index 1,999,999,999. When you search in the upper half of array, beg=1,000,000,001 and end=2,000,000,000. If mid is calculated as (low+high)/2, low+high = 3,000,000,001; which exceeds the range of int, resulting in overflow errors. But mid calculated as beg + (end-beg) = 1,000,000,001 + 999,999,999 = 2,000,000,000; which fits in the integer range.


Python

Binary search in Python.


C++

Binary Search in C++.


Binary Search in Java.

public class Search {

    int BinarySearch( int array[], int num ) { 
      
        int beg = 0;
        int end = array.length - 1;
        while (beg <= end) {

            int mid = (beg + end) / 2;

            if (array[mid] < num) {
                beg = mid + 1;
            } else if (array[mid] > num) {
                end = mid - 1;
            } else if (array[mid] == num) {
                return mid;
            }
        }
        // Return an index -1 if the number in the sorted array does not exist
        return -1; 
    }   

    public static void main(String args[]) {

        int[] array = { 3, 5, 7, 11, 12, 16, 17, 52, 64, 101 };
        Search s = new Search();

        System.out.println("Number 7 found at index : " + s.BinarySearch (array, 7));
        System.out.println("Number 16 found at index : " + s.BinarySearch (array, 16));
        System.out.println("Number 101 found at index : " + s.BinarySearch (array, 101));
        // Binary Search return an index -1 if the number in the sorted array does not exist
        System.out.println("Number 100 found at index : " + s.BinarySearch (array, 100));
    }   
}

Output of Binary Search implementation in Java.

Number 7 found at index : 2
Number 16 found at index : 5
Number 101 found at index : 9
Number 100 found at index : -1

Copyright (c) 2019-2021, Algotree.org.
All rights reserved.