Thread: Difference Between A Linear Search And Binary Search

Hey Guys Im Pretty New To C Programming And Wanted To Know Whats The Difference Between A Linear And Binary Search?

Salem, I am simply just asking a question, hasnt anyone told you never to answer a question with another question???

i think ive got it anyway so tell me if i am correct

linear search: a method of checking for a particular value in a list,one at a time until it is found e.g for loops

binary search: array has to be sorted before a binary search can be done, it splits the array in two.

Binary search is like playing "Guess a Number between 1 and 10", with a smart kid.

He guesses 5. You have to tell him if he's too high, too low, or correct.

If he's too high, then 4 will be the new high value for the search.

If he's too low, then 6 becomes the new low value for the search.

Every guess that is not correct, the high or low keep cutting off the impossible parts of the remaining choices.

Finally, low and high equal each other (meaning the number was not on the list), or the correct value is found.

Compared to linear search, it's HUGELY faster.

One of the biggest differences between the two... along with adak's description... is the number of guesses it takes...

If you are looking for one item in 1023 and it happens to be the last one... A linear search has to do 1023 reads to find it but a binary search will find it in 10. 2047 with a linear search takes twice as long, in a binary search it takes only 1 more try... in fact every time you double the number of items on the list a linear search takes twice as long but a binary search takes only 1 extra try...

The catch is that, as you observed, the list has to be sorted for a binary search and sorting is very slow.