Thread: Logic behind Binary Search?

  1. #1
    Registered User
    Join Date
    Apr 2002
    Posts
    63

    Logic behind Binary Search?

    Hi,
    I was recently asked as to what is the logic behind Binary Logic..and I must say the question made no sense to me..maybe one of you can help me..Thanks..
    Asp

  2. #2
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    The logic behind the search is that if you have an ordered collection of items, you can search for a given item by dividing that collection in half each time until you find what you are looking for.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  3. #3
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    aspand, just do a google search for "binary search tree". You'll get loads of hits, some have interactive examples as well.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    A binary search returns the item being searched for with the minimum number of steps. You start at the middle, if the key is greater then you divide the second half and do the same thing with it.
    Code:
    key = 12
    
    First step:
                    marker
                      |
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
    
    Second Step:
              marker
                |
    11 12 13 14 15 16 17 18 19 20
    
    Third Step:
     marker
       | 
    11 12 13 14
    In three steps a binary search returned the correct value. This isn't so great with a list of 20 values, but when the list gets to be huge, such as one million items, a binary search will find the correct value with no more than 20 steps. This is very very fast.

    -Prelude
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with binary search.
    By StateofMind in forum C Programming
    Replies: 6
    Last Post: 05-06-2009, 02:14 PM
  2. Performance issue!
    By maven in forum C Programming
    Replies: 42
    Last Post: 03-23-2009, 11:57 AM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. binary search or linear search
    By vajira in forum C Programming
    Replies: 0
    Last Post: 06-05-2003, 12:42 PM