Data Structure - Searching - Binary

Binary Search

It is one of the searching technique and it is the fast search algorithm.

-> The runtime complexity is O(log n).
-> It follows divide and conquer principle
-> The elements in the array should be in sorted form

How searching technique works

Let me explain with an example.

Array

14 22 31 68 72 88 89 92

and we want to search the element 22.

Step 1: get the value of middle element in the array

Value = 68 and X = 22, Since X is less than Value I have to move to left side of the array.

Step 2: Get the middle value from the left remaining array.

Value =22 and X=22. Since X and Value are same we return the index value as 1


Algorithm

Lets say we have an array of elements in sorted order called as A
And size of array is n
We have to find the value X

Step 1: Set i =0
Step 2: Set middleElement = A[(int)(i+n)/2]
Step 3: nStep 3: if X == middleElement then Print element found at middle Element Position and Exit
Step 4: if X> middleElement then Go to Step 6
Step 5: Set n = (int)(i+n)/2 and Go to Step 2
Step 6: Set i = (int)(i+n/2) and n = n-i