# 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.     Do 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 Time complexity of Binary Search : Log(N)

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

Python

Python : Binary Search implmentation in Python 3

C++

C++ : Binary Search implementation in C++11

Java : Binary Search implmentation in Java 8

``````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
``````