Searching Algorithms

Linear Search#

• prerequisites
  • none
• how it works
  • iterates one at a time from left to right
• advantages
  • simple to implement
• example
  • when searching through a phone book for an entry under W
  • go page-by-page until you reach W
• O(n)

Binary Search#

• prerequisites
  • the array must be sorted
• how it works
  • start at the middle and check the value
  • if the value is less
    • check the middle value of the left half
  • else the value is greater
    • check the middle value of the right half
  • repeat until the value is found
• advantages
  • much faster than linear search, especially as n increases
• example
  • when searching through a phone book for an entry under W
  • start at M (middle of A-Z)
  • W > M so check T (middle of M-Z)
  • W > T so check W (middle of T-Z)
  • W = W so we’re done
• O(log(n))
• Check out this article to learn more about Binary Search

Jump Search#

• prerequisites
  • the array must be sorted (like Binary Search)
  • traverses the array in “jumps” of √n (n being the array length)
• how it works
  • once the number being checked is greater than the target number,
    jump √n back and then linear search forwards
• advantages
  • unlike binary search, jump search only jumps backwards once
  • in a scenario in which jumping backward is costly,
    jump search might be better than binary search
• example
  • when searching for a frame in a video,
    you would probably skip ahead in intervals of n
  • once you know you’ve passed the frame,
    you start linear searching backwards
• O(√n)
• Check out this article to learn more about Jump Search

Interpolation Search#

• prerequisites
  • the array needs to be sorted (like Binary & Jump Search)
  • the array needs to be uniformly distributed
    • 0 1 4 6 7 231 22 (not uniform)
    • 0 2 4 6 8 10 12 14 (uniform)
• how it works
  • similar to binary search
  • instead of jumping to the midpoint,
    interpolation search uses a formula to calculate a better new position
  • formula: pos = lo + [(x-arr[lo])*(hi-lo) / (arr[hi]-arr[Lo])]
• advantages
  • when done correctly, it’s much faster than binary search
• example
  • when searching through a phone book for an entry under W
  • there’s no point in searching in any section other than W because
    we already know the word must be under that section
• O(log(log(n)))
• Check out this article and this article to learn more about Interpolation Search

Created By: WHS Comp Sci Club Officers