Computer Science A-Level Notes
Binary Search
function binary_search (items, search_item, first, last)
if first > last then
return -1
else
midpoint = (first + last) DIV 2
if items[midpoint] == search_item then
return midpoint
else if search_item > items[midpoint] then
first = midpoint + 1
return binary_search (items, search_item, first, last)
else
last = midpoint - 1
return binary_search (items, search_item, first, last)
endif
endif
endfunction
Elliot Tierney Page 1
, Computer Science A-Level Notes
Binary Tree (Search)
function binary_tree_search (node, search_item)
if search_item == node.data then
return True
elseif search_item > node.data and node.right != Null then
return binary_tree_search (node.right, search_item)
elseif search_item < node.data and node.left != Null then
return binary_tree_search (node.left, search_item)
endif
return False
endfunction
Elliot Tierney Page 1
, Computer Science A-Level Notes
Bubble Sort
procedure bubble_sort(items)
#Initialise variables
num_items = items.length
temp = 0
#Pass through list n-1 times
for pass_number = 1 to num_items - 1
for index = 0 to num_items - 2
#Check if items are out of order
if (items[index] > items[index + 1]) then
#Swap items
temp = items[index]
items[index] = items[index + 1]
items[index + 1] = temp
endif
next index
next pass_number
endprocedure
Elliot Tierney Page 1
Binary Search
function binary_search (items, search_item, first, last)
if first > last then
return -1
else
midpoint = (first + last) DIV 2
if items[midpoint] == search_item then
return midpoint
else if search_item > items[midpoint] then
first = midpoint + 1
return binary_search (items, search_item, first, last)
else
last = midpoint - 1
return binary_search (items, search_item, first, last)
endif
endif
endfunction
Elliot Tierney Page 1
, Computer Science A-Level Notes
Binary Tree (Search)
function binary_tree_search (node, search_item)
if search_item == node.data then
return True
elseif search_item > node.data and node.right != Null then
return binary_tree_search (node.right, search_item)
elseif search_item < node.data and node.left != Null then
return binary_tree_search (node.left, search_item)
endif
return False
endfunction
Elliot Tierney Page 1
, Computer Science A-Level Notes
Bubble Sort
procedure bubble_sort(items)
#Initialise variables
num_items = items.length
temp = 0
#Pass through list n-1 times
for pass_number = 1 to num_items - 1
for index = 0 to num_items - 2
#Check if items are out of order
if (items[index] > items[index + 1]) then
#Swap items
temp = items[index]
items[index] = items[index + 1]
items[index + 1] = temp
endif
next index
next pass_number
endprocedure
Elliot Tierney Page 1
