BINARY SEARCH

• Binary search is simpler and faster than the linear search.
• For an given array of n elements, the basic idea of  binary search is that for a given elements,we 'probe' the middle element of an array.

                     

• We continue in either lower or upper segment of the array depending on the outcome of the probe until we reached the required element.

EXAMPLE:

        Binary search (A,20,0,6)⇨Target 20.

• Element 20 is in the position 6.

Efficiency:

• Best case:O(n)
• worst case:O(log2n)      

Advantages: 

• It requires lesser number of iterations.
• It is a lot faster  than linear search.

Disadvantages:

• Unlike linear search ,it requires the list to be sorted before search can be performed.
• In comparison to linear search, the binary search  technique may seem to be a little difficult to implement.