CODEWITHSUNDEEP
searchbinary-search
GameZone RO
GameZone RO

Reputation: 63

More about binary search

I just learned binary search . I searched about its use.

Among other things I found :

Last three * I did not understand too much. Somebody can explain me please?

Besides, what other uses have?

Upvotes: 0

Views: 91

Answers (1)

Uddalak Bhaduri
Uddalak Bhaduri

Reputation: 83

Binary Search has O(logn) complexity.... which means that if there is a list of 'n' sorted elements, it takes logn comparisons to search for a number. For example your list contains 20 integers: {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}... And you want to search for any number in this list, (think of a number in this list). Now have a look at these set of questions:

Q1. Is 10 the number which you chose? - (y/n)?
-------- if yes then done. (I say "No")
if no then,
Q2. Is the number less than 10 - (y/n)?
-------- I say "No"; which means the number is greater than 10
Q3. Is 15 the number which you chose? - (y/n)?
-------- if yes then done. (I say "No")
Q4. Is the number less than 15? - (y/n)?
-------- I say "Yes"; So now its sure that the number is in between 10 and 15 (i.e., [11,14])
Q5. Is 12 the number which you chose? - (y/n)?
-------- if yes then done. (I say "No")
Q6. Is the number greater than 12? - (y/n)?
I say "Yes"; So now its sure that the number is either 13 or 14
Q7. Is the number 13? - (y/n)?
-------- I say "Yes" else its 14.
(Actually I had chosen 13 as my number)

So in total there are 20 elements, log of 20 (base 2) is 4.32 ~ 4.
So here are my comparisons:
1 st comparison: Is the number less than 10 - (y/n)?
2 nd comparison: Is the number less than 15? - (y/n)?
3 rd comparison: Is the number greater than 12? - (y/n)?
4 th comparison: Is the number 13? - (y/n)?

and i find the number 13 (or 14) in just 4 comparisons, which is true as logn = log20(base 2)=4.

Hence, Akinator application works like this. It works with a large amount of data, and predicts the answer based on the user's reply to Akinator's questions. Reading through Decision Tree and Binary Search Tree might help you :)

Upvotes: 1

Related Questions