0

in the binary search algorithm:

If no items Return false If middle item is 50 Return true Else if 50 < middle item Search left half Else if 50 > middle item Search right half

like can we do the opposite :

Else if 50 < middle item Search right half Else if 50 > middle item Search left half

0

Why???

No, you can't.

Say that the samllest item is 15, the largest is 83 middle item is 56. that's the same as saying "If 50 is less than 56, search between 56 and 83" In a sorted list (it MUST be a sorted list, and I'm assuming a standard, ascending sort), the search would never find the target.

Now,technically, you could do a descending sort. In that case,if 50 < middle, you would search right, but not left. But the standard is to do an ascending sort.

No matter which you use, the keys are these: it has to be a sorted list and the decision has to select the correct side of the midpoint where the target must be, if it is there at all.

5
  • thnx, so it should be already sorted list ..well I supposed it is random – sumer fattoum Dec 8 '20 at 0:14
  • I had a feeling that you missed the sorted requirement. ;-) – Cliff B Dec 8 '20 at 0:36
  • 1
    yes I guess, because I supposed it should be a general algorithm where you can search in any array, so maybe we should firstly use sorting then searching for any type of search – sumer fattoum Dec 8 '20 at 0:42
  • Almost every efficient, high speed search depends on a list being sorted. Exceptions would include a linear search (inefficient) or a hash-based tree/trie. (You'll learn about them in pset5 speller.) – Cliff B Dec 8 '20 at 0:53
  • nice, thank you – sumer fattoum Dec 8 '20 at 1:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .