Hey Guys Im Pretty New To C Programming And Wanted To Know Whats The Difference Between A Linear And Binary Search?
This is a discussion on Difference Between A Linear Search And Binary Search within the C Programming forums, part of the General Programming Boards category; Hey Guys Im Pretty New To C Programming And Wanted To Know Whats The Difference Between A Linear And Binary ...
Hey Guys Im Pretty New To C Programming And Wanted To Know Whats The Difference Between A Linear And Binary Search?
Is google broken?
I mean, "linear search" and "binary search", and do a bit of reading.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
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.