Thread: Binary Search Please check if it's right..

  1. #16
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,666
    > Please check if it's right, i think i'm getting right output, but not sure...
    Some cases to try
    - an array with 0 elements
    - an array with 1 element
    - an array with an even number of elements
    - an array with an odd number of elements
    - an array with a power of 2 elements
    - an array with a prime number of elements
    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.

  2. #17
    Registered User
    Join Date
    Apr 2008
    Posts
    15
    Yes, it does work. But did I implement it right? I followed this animation tutorial :

    http://www.cse.ust.hk/faculty/tcpong...ds/select.html

  3. #18
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Todd Burch View Post
    OK, that fixes it! Thanks.

    Also, the 7 is correct. The algorithm uses it as the last index, not as the number of elements.

    Todd
    You're right, though I intended it to be the number of items rather than the index of the last item. This one is even wrong in my source code. r should be assigned n-1 at the start. This showed up a hole in my unit tests and I'm fixing this now.
    I found two other bugs too, by adding these extra unit tests! I'm not having a good day so far.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary search on strings
    By ckathy in forum C++ Programming
    Replies: 1
    Last Post: 10-02-2007, 05:25 PM
  2. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  3. Binary tree search efficiency
    By ExCoder01 in forum A Brief History of Cprogramming.com
    Replies: 8
    Last Post: 10-23-2003, 10:11 PM
  4. writing/reading from file produces double results.
    By stumon in forum C Programming
    Replies: 4
    Last Post: 03-20-2003, 04:01 PM