Ashlyn Chapman

What's a search problem?

Bad news! Within the last 2 days, someone stole your bike.

You want to find out when.

If you can find the timestamp, you can identify the thief (and maybe the police can arrest them). However, there are 2 days worth of CCTV film to watch to pinpoint the time of the theft. 1 2

That's your search problem -- you need to find 1 thing in an ocean of data.

Instead of watching every minute of CCTV recording, you use a search algorithm to find the time the thief struck.

You pull up the halfway point in the recording. Is the bike still there? Was it stolen yet?

No, your bike is gone.

Now you know that your bike was stolen within the first day of CCTV footage. There is no point in looking for the thief in the second half of the recording. The theft already happened. The thief isn't coming back.

In one simple check, you halved the amount of information we had to search through. You started with 2 days (48 hours) of film, and now know you only need to look through the first 24 hours.

Let's repeat that search technique.

You know the bike was stolen in the first 24 hours of the recording. You jump to the 12 hour mark in the recording. The bike is where you left it. The theft hadn't occurred yet.

The thief stole your bike between the 12th and 24th hour in the CCTV footage.

In 2 steps, you quartered the amount of time you had to search. You repeatedly check the halfway point in the possible period of the theft. Quickly, you discover when the thief stole your bike.

In this example, you see the binary search algorithm in action to crack the search problem.

Here's what you need to know to address a search problem:

When searching for your bike, you know the bike could either be:

  1. where you left it
  2. actively being stolen
  3. missing You are starting with your bike missing and what to find the start, the time, when the thief stole your bike. You use the binary search algorithm to move through the film recording to find a change in the bike's state.

Search problems are unique because you often have heaps of information, but don't know how to sift through it.

You know all the possible states you could end up in. You know which of those possible states you want. The problem is you don't know how to get there.

What steps should you take? How do you pick what step is best when you have many options?

In many problems, you might not know what end state you desire? You don't know what you are pursuing. The challenge here instead is knowing what path to take.

Simply: a search problem is how to find Y in X 3.

Other interesting examples of search problems:

Resources & References

  1. how I learned about the stolen bike dilemma

  2. binary search to find bike thief

  3. wikipedia

#ai #ds-algs