python (12.9k questions)

javascript (9.2k questions)

reactjs (4.7k questions)

java (4.2k questions)

java (4.2k questions)

c# (3.5k questions)

c# (3.5k questions)

html (3.3k questions)

Questions - proof-of-correctness

How to know if incorrect binary search algorithm always terminates without testing

Consider the following algorithm where target = 13 and array = [5,10,15,20,25] where N = length of array lo = 1 hi = N while lo < hi: mid = (lo+hi)//2 if target >= array[mid]: lo...
test-img

Fried_Mind

algorithm

binary-search

proof

proof-of-correctness

Votes: 0

Answers: 2

Latest Answer

In a binary search, if you want to make sure that the loop terminates, then you need to make sure that the range (hi-lo) shrinks with every iteration. You also need to make sure that lo and hi are wi...
test-img

Matt Timmermans

Posts

Questions

Blogs

Jobs