Tutorials

Searching Techniques


Binary Search


Linear search is bit slow as it needs to compare each element from beginning to end to find the desired element.

 

So binary search is extremely efficient algorithm as it searches required item in minimum possible comparisions.

 

Binary search is possible only on sorted array.

After sorting the array, binary search is performed as below:

  1. First we need to calculate the middle index of the array.
  2. Compare the element at middle index with item to be searched.
  3. If the middle element is the required element then search is successful.
  4. If middle element is greater than desired item then search only the first half of the array.
  5. If it middle element is less than desired item then search only the second half of the array.
  6. Step 1 to 5 is repeated on the part of array which is next to be searched and will be repeated until desired element is found.

In binary search every time the number of element that needs to be searched is reduced by almost half thus making it more efficient than linear search.

 

See the below diagram to understand the binary search work in detail.

  binary search by tutorialsinhand

 

 

Example on binary search

Suppose we are given a sorted array as shown below:

          binary serach by tutorialsinhand.com

 

In the above array we need to search 78.

 

Step I:

first index = 0, last index = 6

mid = (first index + last index)/2= (0+6)/2 = 6/2 = 3

 

We have marked element at index 3 with circle. This is the mid value.

 

Step II:

a[mid] < item to be searched, 

first index = mid + 1 = 3 + 1 = 4

 

Now second part of the array will be searched as shown below:

 

binary search by tutorialsinhand.com

 

Step III:

first index = 4, last index = 6

mid = (first index + last index)/2= (4+6)/2 = 10/2 = 5

 

Step IV:

a[mid]=item to be searched.

 

Binary search completes.



Please Share this page
Views : 12