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”
~~~