2.3.4 searching algorithms

binary search

• can only be applied on sorted data

• efficient for large data sets as it discards half the data after each iteration

• works by finding the middle element in a list of data, comparing it to the element being searched for, before deciding which side of the data the desired element is to be found in

  • if list cant be divided, round to nearest whole number

• the unwanted half of the data is then discarded

• the process is repeated until the desired element is found or until it is known that the desired element doesn’t exist in the data

linear search

• doesn’t require data to be in order

• efficient for smaller data sets, inefficient for large data sets

• starts at the first item in the list and checks each item one by one

• when the item being searched for is found the search ends

ADV breadth first

• more efficient when the data being search for is closer to the root

• in general has abetter time complexity than depth first

ADV depth first

• more efficient when the data being searched for is further down the tree

• memory requirement is linear

• can be written recursively to aid understanding

• DIS

• in large trees it may never return a value

binary search pseudocode

binary search python

linear search pseudocode

linear search python