Difference Between A Linear Search 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 ...

  1. #1
    Registered User
    Join Date
    May 2011
    Posts
    4

    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?

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,659
    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.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    May 2011
    Posts
    4
    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.

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  5. #5
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linear search
    By kingkobra in forum C++ Programming
    Replies: 0
    Last Post: 12-03-2009, 01:42 PM
  2. A Binary Search Tree of... Binary Search Trees...
    By SlyMaelstrom in forum C++ Programming
    Replies: 5
    Last Post: 12-10-2005, 01:12 PM
  3. Search Engine - Binary Search Tree
    By Gecko2099 in forum C Programming
    Replies: 9
    Last Post: 04-17-2005, 02:56 PM
  4. no. of comparisons in linear/binary search
    By alice in forum A Brief History of Cprogramming.com
    Replies: 7
    Last Post: 06-05-2004, 10:55 PM
  5. binary search or linear search
    By vajira in forum C Programming
    Replies: 0
    Last Post: 06-05-2003, 12:42 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21