Wednesday, 30 November 2011
Tuesday, 29 November 2011
Binary Search
Very useful searching algorithm, in every step the number of data, which is going to be sorted will cut into half (fig 1). But keep it in your mind that it works on only sorted data.
Let N be the number of data then,
in worst case the comparison will be done log2(N) + 1 times. And in case of linear searching, the number of comparison would be N.
For example: if we are going to search a number among a million others, in the worst case scenario, the number of comparison would never be exceeded 20. But in case of linear searching algorithm, the number of comparison would be 1.000.000
Source code :
Let N be the number of data then,
in worst case the comparison will be done log2(N) + 1 times. And in case of linear searching, the number of comparison would be N.
For example: if we are going to search a number among a million others, in the worst case scenario, the number of comparison would never be exceeded 20. But in case of linear searching algorithm, the number of comparison would be 1.000.000
Source code :
Saturday, 26 November 2011
Subscribe to:
Posts (Atom)