Tutorial 5

🎯

Binary Search

9618 A-Level

i

It may be useful to search (CTRL + F) for "binary search" questions in the (combined) past papers

If you find any bugs/edge cases in this code, please contact me

1

Binary Search

For IGCSE/O-Level/AS, you should be familiar with linear search - i.e. checking every element one by one until you find the element or until you reach the end of the array, file etc

It is important to note that for an unsorted array, linear search is the only option - it's simple, but slow, with a time-complexity of O(n) meaning that the performance degrades linearly with the number of data items - e.g. if we have an array with 100 elements, we might have to perform 100 comparisons; if we have an array with 1 trillion elements, we would have to do 1 trillion comparisons in the worst case (the item not being found)

In contrast, if and only if the array is sorted, we can use binary search - the way this works is as follows:

  1. Create pointers to the start, middle and end elements of the array
  2. If the element you are searching for is equal to the middle element, return/set a flag to true - if it's smaller, update the start and end pointers to now search the left half of the array; if it's bigger, update the pointers to search the right half of the array
  3. Repeat step 2 until you find the element, or return/set a flag to false if the start pointer becomes greater than the end pointer (since this means you have searched all elements and not found it)

More detailed comments can be seen in the code

DECLARE nums : ARRAY[1:9] OF INTEGER DECLARE start, mid, end, target : INTEGER DECLARE found : BOOLEAN nums ← [1, 2, 3, 4, 5, 6, 7, 8, 9] start ← 1 end ← LENGTH(nums) found ← FALSE target ← 3 //loop while not searched whole array and not found element WHILE start <= end AND found = FALSE DO //get middle element - will have one more element on right if even sized sub-array - e.g. mid of [1,2,3,4] will be 2 - i.e. 1 element is left of it, 2 elements are to the right mid ← (start + end) DIV 2 //next 2 statements are just to aid understanding - don't need them in the exam OUTPUT "Start: ", start, " | Mid: ", mid, " | End: ", end, " | Current Element: ", nums[mid] //added to help visualise algorithm steps - not required for binary search itself CALL DisplaySubArray() IF target = nums[mid] THEN found ← TRUE ELSE IF target > nums[mid] THEN start ← mid + 1 //search right half ELSE end ← mid - 1 //search left half ENDIF ENDIF OUTPUT "-----" ENDWHILE IF found = TRUE THEN OUTPUT target, " exists!" ELSE OUTPUT target, " doesn't exist..." ENDIF //added to help visualise algorithm steps - not required for binary search itself PROCEDURE DisplaySubArray() DECLARE index : INTEGER DECLARE arrStr : STRING arrStr ← "" FOR index ← start TO end arrStr ← arrStr & NUM_TO_STR(nums[index]) IF index < end THEN arrStr ← arrStr & ", " ENDIF NEXT index OUTPUT "Searched sub-array: [" & arrStr & ']' ENDPROCEDURE

Extension details/answers will be added: binary search test scores