Binary Search Algorithm Confusion

Question

I've been reading some binary search algorithms I found on the internet, and I noticed this block of code within all examples I have encountered.

if (query > contents[midIndex])
{
    minIndex = midIndex + 1;
}
else if (query < contents[midIndex])
{
    maxIndex = midIndex - 1;
}

Why is that though? I tried doing this:

if (query > contents[midIndex])
{
    minIndex = midIndex;
    midIndex = (minIndex + maxIndex) / 2;
}
else if (query < contents[midIndex])
{
    maxIndex = midIndex;
    midIndex = (minIndex + maxIndex) / 2;
}

That code works in all the testing I've done, and isn't it faster? If it isn't faster, can someone explain the logic of the first snippet of code?

I expect you're doing the same thing as the examples (except you aren't eliminating the value at midIndex as you should be, hence their +- 1). Look for more code where the midIndex gets re-calculated for the next loop. — Collin Green
– Collin Green, Commented Mar 20, 2012 at 3:09

Dr.Kameleon · Accepted Answer · 2012-03-20 03:12:08Z

1

Well, all I can say is that, the first part is NOT binary search at all. (+ it doesn't even seem to recalculate the midIndex variable)

The purpose of binary searches is to be "focusing" the searches in "halves" of the total range until the spectrum has been narrowed down to the element we've been looking for...

answered Mar 20, 2012 at 3:12

Dr.Kameleon

22.8k21 gold badges124 silver badges240 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

No_name Over a year ago

academics.tjhsst.edu/compsci/CS2C/U2/bisearch.html en.wikipedia.org/wiki/Binary_search_algorithm#Iterative are wrong?

Dr.Kameleon Over a year ago

Nope; but you just forgot to mention the int imid = (imin + imax) / 2; part (I'm referring to the Wikipedia article) in the initial code you posted... it makes quite a difference, huh?

No_name Over a year ago

even then, isn't the +-1 unnecessary?

Dr.Kameleon Over a year ago

Nope, it's not. And here's why : let's say you start with the range (0..10). Is our test_element > element[5]? If yes then search to the "higher range"... but which one is that? (5..10)? or (6..10)? In a few words, there is no point in "rechecking" element[5], since we already know it's NOT the one we were looking for... (test_element was GREATER than element[5] right?) That's what we would do, even if it was LESS than... search in (0..4), and NOT in (0..5)... ;-)

No_name Over a year ago

yet another question, why are most of the conditions on the while loop (imax >= imin)? is the equal sign necessary?

|

Neil Luo · Accepted Answer · 2012-03-20 03:22:47Z

0

 You can achieve binary search by loop or recursion and there are so many code

in the Internet.The principle of the binary search is like search one page in a book.The pages is orderd and you will look for one half every time.This is the principle of your first snippet of code.

 About the speed of the two segments,I think they are not whole.Binary search is

not so easy and there are some details should be noticed.Please google for it!

answered Mar 20, 2012 at 3:22

Neil Luo

13 bronze badges

Collectives™ on Stack Overflow

Binary Search Algorithm Confusion

2 Answers 2

6 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related