Two equivalent formulations of the binary search algorithm

First version:
procedure binary search (x: integer, a_1, a_2,\dots, a_n: increasing integers)
i:= 1
j:= n
while i <j
m:= \lfloor \frac{i + j}{2}\rfloor
if x>a_m then i:=m+1
else j:=m
if x = a_i then location :=i
else location :=0
return location

Second version:
procedure binary search (i, j, x: i, j, x: integers, 1 \leq i \leq j \leq n, a_1, a_2,\dots, a_n: increasing integers)
if x = a_m then
return m
else if (x <a_m and i <m) then
return binary search(i, m-1, x)
else if (x > a_m and j > m) then
return binary search(m + 1, j, x)
else return 0
{output is location of x in a_1, a_2, \dots, a_n if it appears; otherwise it is 0}

This entry was posted in Discussion. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *