Searching for an item in an array is a common need. Software developers should know the possible algorithms for searching and which is best for different use cases.
Agari used Radix trees to optimize their IP address search engine - their efficiency went from 0(n) (searching an array) to O(log n).
Participants will be able to:
What is an algorithm?
Think about a shuffled deck of cards. Let’s say you’re looking for the 6 of hearts. How do you find it? You could just start grabbing random cards until you find it. If you grab a card and say “this isn’t it” and put it back, you really could be looking for a long time. Starting at the top of the deck and looking at each card one by one, you’re guaranteed to find it. This is the basis of a linear search.
If you have a phone book, and you’re looking for Jessica Smith, do you start on page 1 and read every name until you find her? Probably not. By starting in the middle, flipping larger chunks of pages until you get to the Ss, then eventually finding Smith, then finding Jessica eliminates a TON of time. This is the idea behind a binary search.
All of these algorithms are pretty common and have standard implementations in most programming languages. But understanding how they work and when to use one over another will help you write better software.
Watch the videos to learn more details about linear and binary search algorithms!
Slides: Searching algorithm (slides)
Video:Searching algorithm (video walkthrough of slides)
Write a linear search to find a given item in an array. The function should take in an array of strings and a string to search for, and return whether that string is in the array
Write a linear search to find the largest item in an array. The function should take in an array of integers and return the largest integer.
Say you have an array and want to find the number closest to a given number n. Write a linear search to find the closest number. E.g. if the array is [4, 1, 6, 8] and n=3, your function should return 4.
How long does linear search take for large arrays vs binary search? Draw a graph with values 1 to 100 on the x-axis. Graph a linear function (y=x) and a log function (y=log2(n))
Make a cheat sheet answering the following questions for linear search and binary search: