二元搜尋 Binary Search
用二元搜尋法在1~6中搜尋4
疊代
function search(list, target)
var left = 0, right = list.length - 1
while left <= right
var middle = 取出list中點
if list[middle] == target
return middle
// 比目標大，再搜索左半邊
else if list[middle] > target
right = middle - 1
// 比目標小，再搜索右半邊
else if list[middle] < target
left = middle + 1
end if
end while
return -1
end function
遞迴
function search(list, target, left, right)
if left > right
return -1
end
var middle = 取出list中點
if list[middle] == target
return middle
// 比目標大，再搜索左半邊
else if list[middle] > target
return search(list, target, left, middle - 1)
// 比目標小，再搜索右半邊
else if list[middle] < target
return search(list, target, middle + 1, right)
end if
return
end function