binary searches

This is a discussion on binary searches within the C Programming forums, part of the General Programming Boards category; Just curious, but suppose I have a set of numbers, 1 through 15, in numerical order. Is there an equation ...

  1. #1
    Registered User
    Join Date
    Nov 2001
    Posts
    3

    binary searches

    Just curious, but suppose I have a set of numbers, 1 through 15, in numerical order. Is there an equation which can determine the number of searches it would take using a binary search to find a specific item? i.e., I know it takes 4 searches if I am searching for the number 1, but if I want 5? 14? Is there a better way of doing this than w/ pencil and paper?

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Simple, find out what power of two yours is closest to, rather, the next closest higher if not an exact match, find what bit number that is, add one, that's how many searches it takes.

    Example: 8 numbers = 3rd bit = 3 searches:
    1-8
    1-4 or 5-8
    1-2 or 3-4 or 5-6 or 7-8
    1 or 2 or 3 or 4 or 5 or 6 or 7 or 8

    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User
    Join Date
    Nov 2001
    Posts
    65
    noOfSearches = ceiling(lgn) logarithm in base 2.

    This gives you the maximum number of searches where n is the number of elements in the sequence. If the item is not in the sequence you make an extra operation too.

  4. #4
    Registered User sballew's Avatar
    Join Date
    Sep 2001
    Posts
    157
    Quzah: I know this is simple for you, but me being a NB, it is not so simple, not right off the bat at least.

    I followed you up to

    Example: 8 numbers = 3rd bit = 3 searches
    But what does the following mean???


    1-8
    1-4 or 5-8
    1-2 or 3-4 or 5-6 or 7-8
    1 or 2 or 3 or 4 or 5 or 6 or 7 or 8
    Sue B.

    dazed and confused


  5. #5
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    I can't believe y'all never played this game before...

    I'm thinking of a number, from 1 - 64... what's the best way to guess it?

    If you want to minimize your worst case # of guesses, then you just pick the middle number each time (that is, (1 + 64) / 2)...

    32? Lower, so 1 - 31 -> 16
    16? Higher, so 17 - 31 -> 24
    24? Lower, so 17 - 24 -> 20
    20? Higher, so 21 - 24 -> 22
    22? Lower, so 21
    21? Bingo!
    See? I found it in 6 steps. Not bad, not compared to 21 most certainly.

    Notice that there are cases where I had to round off. To find the worst case, I should have picked the range which gave me more values to eliminate.... for example, 1 - 31 isn't as many numbers as 33 - 64. We can do this by always rounding down and always having to pick the higher range, or by always rounding up, and having to always pick the lower range. Lower ranges are easier to deal with, so I'll try it rounding up...

    33? Lower, so 1 - 32 -> 17
    17? Lower, so 1 - 16 -> 9
    9? Lower, so 1 - 8 -> 5
    5? Lower, so 1 - 4 -> 3
    3? Lower, so 1 - 2 -> 2
    2? Lower, so 1
    1? Bingo!
    Aha, so the actually worst case, using a binary search is not 6 steps, as in the previous example, but 7.

    So to find the worst case for say, 1 to 15, just use the same process. Always round up, and always have it turn out that the lower range is the correct one...
    or always round down and have it turn out that the higher range is the correct one.

    As it turns out, the time it takes to find a number this way is related to the base 2 logarithm of the range.
    Last edited by QuestionC; 12-06-2001 at 05:43 PM.
    Callou collei we'll code the way
    Of prime numbers and pings!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 04-02-2006, 09:31 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. Binary searches
    By Prezo in forum C Programming
    Replies: 4
    Last Post: 09-10-2002, 09:54 PM

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