Home → Blogs → [email protected] → Getting a Program Right (3) → Full Text

# Getting a Program Right (3)

By Bertrand Meyer

March 2, 2020

This is the third article about a seemingly naïve question: how do we write a binary search program? The first article appeared here.

The first program attempt was wrong. The second article introduced a new one:

--  Program attempt #2.

from

i := 1 ; j := n

until i = j or Result > 0  loop

m := (i + j) // 2         -- Integer division

if t [m] ≤ x then

i := m  + 1

elseif t [m] = x then

Result := m

else                         -- In this case t [m] > x

j := m - 1

end

end

The question was: it right?

Again no.  A trivial example disproves it: n = 1, the array t contains a single element t [1] = 0, x = 0. Then the initialization sets both i and j to 1, i = j holds on entry to the loop which stops immediately, but Result is zero whereas it should be 1 (the place where x appears).

Here now is attempt #3, let us see it if fares better:

--  Program attempt #3.

from

i := 1 ; j := n

until i = j loop

m := (i + j + 1) // 2

if t [m] ≤ x then

i := m  + 1

else

j := m

end

end

if ≤ i  and i n then Result := i end

-- If not, Result remains 0.