Binary Search Confusion (1 Viewer)

[sig]

After reading Sam Davis's algorithm on Binary Search which reads

BEGIN BinarySearch
  Set Low to 1
  Set High to number of items in list
  Set Found to False
  Get ItemToFind
  WHILE High > Low AND Found = False
    Set Middle to INT((Low + High)/2)
    IF ItemToFind < Item(Middle) THEN
      Set High to Middle - 1
    ELSEIF ItemToFind = Item(Middle) THEN
      Set Found to True
    ELSE
      Set Low to Middle + 1
    ENDIF
  ENDWHILE
  IF Found = True THEN
    Display "Found"
  ELSE
    Display "Not Found"
  ENDIF
END BinarySearch

If I had 5 Items and the item I was trying to find was number 4 in the list...
After First Part the Low would be Middle + 1 Therefore Number 4

2nd Pass would involved middle being [(4 + 5)/2] which would be 4.5 so rounded to 5 I presume?

This is when I get confused since the target item is smaller then the middle it would make High to Middle - 1 (Thus 4)

But then both High and Low would equal 4 and the number would not actually be found

Can someone please clear the confusion

Thanks

ps. sorry about the >>> I dunno how to indent

 

[acmilan]

Its truncated, so the decimal is removed and not rounded up. So the middle for the second pass would be 4 which means it will find it since it is the middle

 

[Wild Dan Hibiki]

Its truncated, so the decimal is removed and not rounded up. So the middle for the second pass would be 4 which means it will find it since it is the middle

yep yep, i was just about to say that... seriously though, good thing i opened this thread

 

[Freedom_Dragon]

Sorry about that Sig...

I forgot to mention that when i wrote those summaries on algorithm.

Yer basically u round it down.

 

[Seraph]

Question

Set High to Middle - 1

is this ideally a more optimized way performing a binary search? where we move it one up or one down , and is this vital in the binary search algorithm?

Furthermore when there is a multiple choice question giving a set of numbers and saying how many searches will ti take to find blah blah number , wont the answer chagne depending on whether we use this method or not?

 

[Freedom_Dragon]

IF Target < Array_Item(Middle) THEN
Upper=Middle-1
ELSE
Lower=Middle+1
Most important. Very Vital.
In order to determine where the target is located (lower half or upper half) u would need to know "Low" & "High" + them together to obtain "Middle".
The target exist either in the lower half or upper half. One half is discarded, thus getting closer to finding the target .
A new "Low" Lower=Middle+1 or "High" Upper=Middle-1 & "Middle" is obtained.This process is repeated until the target is found.

This is the main concept. Besides... what other binary search method could u use? U wouldnt use a linear search for an ordered array.
REPEAT Middle=Int(Lower+Upper)/2
IF Array_Item(Middle)=Target THEN
Found=True
FoundPosition=Middle
ELSE
IF Target < Array_Item(Middle) THEN
Upper=Middle-1
ELSE
Lower=Middle+1

Hope That Helped

 

[Seraph]

ehh never the mind

thanks anyway

 

[jesterofenglish]

Heads up

  WHILE High > Low AND Found = False

In case you didn't know, there is a problem with this line when you use test data such as:

[1|5|8|10|12|16|20|33]

Can you spot it? It's an easy fix.