Searching & Sorting
Linear Search
Binary Search
Non-recursive
- Compute index of array midpoint: mid = (low+high)/2
- Compare the value at midpoint with key. if match occurs, return the index mid to locate the key
- key < A[mid] : key must lie within the lower half. new boundaries are low=0, high=mid-1
- key > A[mid]: key must lie within upper range. new boundaries are low=mid+1, high
- if key not in list, low > high, return -1
Recursive
same as above, except
if key < A[mid]: return recursiveBinarySearch(A[:mid], key)
if key > A[mid]: return recursiveBinarySearch(A[mid+1:], key)
Sorting Algorithms
Bubble sort
insertion sort
NOT TESTED FOR UWA1
Quick sort
Merge sort
