Linear searching

A linear search will start at the first index in the array and compare the search term to every item until that item is found or the end of the array is reached.

• Time complex

Algorithm

Procedure LinearSearch
myArray(6) Is Integer
SearchValue Is Integer
Found id Boolean
Set Found = False

Input SearchValue

For I = 0 to 6
	If SearchValue = myArray(i) then
	Set Found = True
	Output “Search Value found at position”, I
	End If
End For
If Found = False
	Output “Search Value not Found.”
End If

Binary searching

<aside> 💡 Divide and conquer (recursive)

</aside>

• Requires the initial array to be sorted before searching
• The array is split into two on each check
• More efficient than linear search
• HAS TO BE ORDERED
• Time complexity: O(logn)
• Space complexity: O(logn)

Steps

1. Flag equals False
2. Check the midpoint
3. Is the value to be found higher or lower than the midpoint?
4. Change either the lower or upper bound by adding or taking away from the midpoint