Binary Search Algorithm Testing Repeated Values

Question

The python code below seems to work fine. If I change the code as per the comments, it still seems to work. Are there conditions where the algorithm will fail if I use high = middle instead of high = middle - 1 and low = middle instead of low = middle + 1?

haystack = [3,5,7,8,9,23,65,89,100]
needle = 89
low = 0
high = len(haystack)

while (low < high):
  middle = (high + low)//2
  if (needle < haystack[middle] ):
     high = middle - 1 # what about just high = middle?
  elif (needle > haystack[middle]):
    low = middle + 1 # what about just low = middle?
  elif (needle == haystack[middle]):
    print ("The needle was found at index " + str (middle))
    break

since middle is already checked for, why would again assign middle to low or high? — mighty_dev
– mighty_dev, Commented Mar 5, 2019 at 15:54
your posted code isn't well aligned i guess?, im not sure: i dont think it will fail but slower — Hasan alattar
– Hasan alattar, Commented Mar 5, 2019 at 16:04

Omer Ben Haim · Accepted Answer · 2019-03-05 16:03:12Z

2

That's because you are considering only on cases where the value is in the list (Maybe there is a case where the list contains the element and these lines are needed but i couldn't think of one) think of the following simple case:

haystack = [1,2]
needle = 3
the rest of the code...

you will be stuck in an infinite loop without the current version of the code.

Note: as @vivek_23 mentioned you are already checking middle so there is no need for that extra iteration.

answered Mar 5, 2019 at 16:03

Omer Ben Haim

7057 silver badges14 bronze badges

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

3 Comments

Robin Andrews Over a year ago

I get that I have already checked middle - I;m just wondering about if/when this could break the algorithm. I'm not concerned about efficiency so much.

Robin Andrews Over a year ago

Could you please explain why the infinite loop?

Omer Ben Haim Over a year ago

middle = (high + low)//2 --> middle =1 --> needle > haystack[middle] --> low = 1 --> low < high --> ....

Mark Ransom · Accepted Answer · 2019-03-05 16:21:47Z

0

In order for the loop to complete, each iteration must decrease the range by at least 1. If it doesn't you get an infinite loop.

If you ever reach a point where low is an even number and high = low+1, the calculation for middle will always return low. You will continually test the same location.

answered Mar 5, 2019 at 16:21

Mark Ransom

310k44 gold badges423 silver badges660 bronze badges

Comments

eric · Accepted Answer · 2019-03-05 16:40:40Z

The explanation as to why you would enter an infinite loop has to do with your condition:

while (low < high):

Not updating the conditions (low or high) would mean that your loop condition does not change and low (if it begins lower than high) will forever be less than high.

Another note is, it would help (you) to break code up into functions. It will make the debugging process easier for you in the future. Here's a not-so-pythonic implementation:

def binary_search(sorted_list, target_value, low, high):
    if (low > high):
        return False
    mid = (low + high) // 2

    if (mid == 0 and sorted_list[mid] != target_value):
        return False
    if sorted_list[mid] == target_value:
        return True
    elif sorted_list[mid] < target_value:
        return binary_search(sorted_list, target_value, mid + 1, high)
    else:
        return binary_search(sorted_list, target_value, low, mid)

If you want to ensure you can reach every item in a list, try testing if your algorithm finds everything in the list:

sorted_list = [1, 2, 3, 4, 5, 6, 7, 8, 8, 9]
not_in_list = 42


def test_binary_search(sorted_list):
    for each_item in sorted_list:
        found = binary_search(sorted_list, each_item, 0, len(sorted_list) - 1)
        if not found:
            print("{} not found by binary_search".format(each_item))
        else:
            print("found {} ".format(each_item))


test_binary_search(sorted_list)

Similarly, you'd like your algorithm to behave correctly when given an item that is not in your list.

def test_item_not_found(sorted_list, item):
    expected = False
    actual = binary_search(sorted_list, item, 0, len(sorted_list) - 1)
    status = "Passed" if actual == expected else "Failed"
    print("status {} expected: {}, actual: {}".format(status, expected, actual))


test_item_not_found(sorted_list, not_in_list)

Collectives™ on Stack Overflow

Binary Search Algorithm Testing Repeated Values

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related