Linear & Binary Search Flashcards
Runtime of linear search on an unsorted array/arraylist
O(n)
Runtime of binary search on a sorted array/arraylist
O(logn)
Most effective search to perform on an unsorted array/arraylist?
Linear Search O(n)
Most effective search to perform on a sorted array/arraylist?
Binary Search O(logn)
How do you perform linear search?
By checking EVERY spot in an array/arraylist
How do you perform binary search?
Guessing game! We check the halfway points and say “lower or higher”. MUST BE SORTED!
low -> lowest index
high -> length - 1 (last index)
mid -> low + high / 2 (if this results in a decimal value- we ONLY focus on the whole number value [ei: 6.5 = mid -> 6])
Runtime of comparing two unsorted lists to one another
n^2
Runtime of comparing one sorted list to one unsorted list
n*logn
or
nlogn
Runtime of comparing two sorted lists to one another
2n
How do you find the low when performing binary search?
index 0
How do you find the high when performing binary search?
length of list - 1
How do you find the mid when performing binary search?
high + low / 2
