Searching Algorithms

Question 1

Binary Search

Answer 1

Binary Search: Only applied on sorted data
- Works by finding middle element in list before deciding which side of the data the desired element is to be found in
- Unwanted half of data then discarded & process repeated until desired element is found or until known that desired element doesn’t exist in data
- Time complexity is O(log n)

Question 2

Binary Search Psuedocode

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

Linear Search

Answer 3

Linear Search: Most basic searching algorithm
- Searches each item individually until found
- Time complexity is O(n)

Question 4

Linear Search Psuedocode

Answer 4

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 
return “Not found in data”