Difference between revisions of "Binary Search"
Proj user16 (talk | contribs) (→Binary Search) |
Proj user16 (talk | contribs) (→Binary Search) |
||
| Line 9: | Line 9: | ||
Below Image shows the formation of the algorithm in binary tree structure. | Below Image shows the formation of the algorithm in binary tree structure. | ||
| − | [[File: | + | [[File:CmpE243_F16_Binary Search Algorithm.png]] |
'''Code Snippet''' | '''Code Snippet''' | ||
Revision as of 22:59, 2 December 2016
Binary Search
The Drawback of the Linear search was that, it was not efficient enough when the data set was huge. This Drawback is eliminated when Binary Search algorithm is used. But the drawback of this algorithm is that the data set has to be sorted. In this Algorithm the data set would be divided into 2 equal parts in every iteration till the required element is found or till the case when further equal division is not possible. This algorithm is similar to searching for a particular page in a book. Say for example a book is having 20 pages and 8th page is to be found. Now equal halves of 20 page book is 0-10 pages block and 11-20 pages block. So 8th page falls under 0-10 page block. This continues for few more iterations, till 8th page is reached.
This method needs [log2n]+1 comparisons, i.e O(log n) in Big O notation, i.e. for Thousands of records, it needs about five to six comparisons, which is way better than Linear search.
Below Image shows the formation of the algorithm in binary tree structure.
Code Snippet
