2. 3. 4 Searching Algorithms

Question 1

Binary Search

Answer 1

• Can only be applied on sorted data
• Finds middle element, determines which side desired element is on
• Unwanted half discarded; process repeats till desired element found
• Or when it becomes known desired element does not exist in the data
• Half data discarded with each iteration, makes binary search very efficient
• Time complexity is O(log n)

Question 2

Pseudocode for Binary Search

Answer 2

• A = Array of data
• X = Desired element
• low = 0
• high = A.length -1
• while low <= high:
• mid = (low high) / 2
• if A[mid] == x:
• return mid
• else if A[mid] > x:
• high = mid -1
• else:
• low = mid + 1
• endif
• endwhile
• return “Not found in data”

Question 3

Example of Binary Search

Answer 3

• Find location “Dylan” using a Binary search on the data below
• |0||1||2||3||4||5||6||7||8|
• |Alice||Bob||Charlie||Dylan||Ellie||Franz||Gabbie||Hugo||Ingrid|
• First step is to find the middle position, 8 / 2 = 4, Ellie in position 4
• We then observe the values on the left (0-3) and right (5-8)
• “Dylan” is not on the right so values 4-8 are discarded from the list
• Middle value is calculated again, 3 / 2 = 2 (round to nearest whole number), Charlie is in position 2
• We then observe the values on the left (0-1) and the right (3)
• “Dylan” is not on the left so the values 0-2 are discarded from the list
• Middle value is calculated for the final time, 3 + 3 / 2 = 3, Dylan is in position 3
• We have found our desired data “Dylan”, we return the position 3

Question 4

Linear Search

Answer 4

• Think of this algorithm like going along a bookshelf one by one till you get to the book you wanted
• The books are in no particular order (algorithm works with unordered list)
• Sometimes algorithm gets lucky (get it straight away), sometimes it’s very inefficient (near last few items)
• It is a very easy and basic algorithm to implement but it all comes down to luck for its efficiency

Question 5

Pseudocode for Linear Search

Answer 5

• A = Array of data
• x = Desired element
• i = 0
• while i < A.length:
• if A[i] == x:
• return i
• else:
• i = i + 1
• endif
• endwhile

Question 6

Example of Linear Search

Answer 6

• Find “Mango” using a linear search on the data below
• |0||1||2||3||4|
• |Banana||Orange||Apple||Kiwi||Mango|
• Inspect 0, not Mango, move on, inspect 1, not Mango, move on
• Inspect 2, not Mango, move on, inspect 3, not Mango, move on
• Inspect 4, it is Mango, algorithm returns 4 and terminates