Binary search technique

What is Binary search?
The binary Search is a Divide and Conquer search algorithm. The binary search can be implemented only sorted list or array of elements.
The binary search process starts with searching the element at the middle of the array or list and comparing the search value with the element in the middle of the list, if the search value is less than the element at the middle of the list then the search process the search value to the list up to the middle element and if the search value is greater than the element at the middle of the list then the search the value from middle element to the end of the list.
Complexity of binary search is O(log n).

Advantage and disadvantage of binary search:-
Advantage:- Binary search is an optimal searching technique using which we can search element very efficiently.
Disadvantage:- This technique requires the list or array to be sorted.

Algorithm of binary search:-
Steps:-
1. Compare search value with the middle element of the list.
2. If search value matches with middle element of the list, we print the message element found.
3. Else If search value is greater than the mid element, then search value can only lie in right half sub-array after the mid element. So we recur for right half.
4. Else If search value is smaller than the mid element, then search value can only lie in left half sub-array after the mid element. So we recur for the left half.

C implementation of binary search:-

Output:-

Java implementation of binary search:-

Output:-

Complexity analysis:-
To calculate complexity of binary search or any other kind of searching, we just calculate the number of comparisons.
In case of binary search, If search element is in the middle of the array the loop will always execute only one time and so the best case complexity of binary search will be C(n)=O(1).
If search element is not is the middle of the array then array will be half i.e.