[MUSIC]
All right, in this lesson we're gonna learn some core algorithms for
searching for data.
Searching for data you probably do every day, many times a day.
And so we're gonna focus on some of the fundamentals of how to search for data and
how to do that quickly.
So by the end of this video,
you're going to be able to motivate why we want to search for data.
As well as to be able to write code to perform linear search, and
then we'll build on this in subsequent videos.
So let's start off with a motivating example.
Say I'm going on a trip, which I am.
I'm going on a trip and I wanna plan my airline travel, and in order to do so,
if you've booked airline tickets online,
you probably know that those airline ticket booking sites
use a three letter code for the airport that you're trying to book from.
So I'm coming from my hometown of San Diego and
I wanna figure out what is the three letter code for the airport in San Diego.
So there's a lot of ways I can find this information.
And probably one of the most popular ways is I can go to my favorite search engine
like Google and type in this query into Google and
Google will go off and search the information that's on the web
to find me a page that will hopefully answer my question.
Now, this is an example of search.
In fact an Internet search is a fairly complex search.
So there's a lot going on here in order to organize all the data and
return me results quickly.
Results that I find useful and so on and so forth.
So this kind of search is a little bit beyond the scope of this course.
But the idea is the same.
We have a big repository of data and I wanna find some information
in that data in order to answer some questions about it.
This is kind of fundamental to almost everything that we do in Computer Science.
So, let's simplify the problem slightly.
Instead of searching the entire Internet,
I'm gonna take a subset of the data on the Internet, a very small subset.
That I can find in a file called airports.dat,
which is on the website, whose url that you see here.
And, this file has information about,
almost, 7,000 different airports around the world.
And it's represented in terms of a number of different fields.
So each line in the file has a number of different comma separated fields.
Those fields include a unique ID inside this database, the name of the airport,
the name of the city that the airport is located in, the name of the country, and
that three letter airport code.
And a bunch of other information as well which you can find out by
going to that URL.
So I'm gonna be searching within this lesson in only this data,
not on the whole Internet.
So, what I'm going to do is, I'm going to read in all of this data into my Java
program, and then I'll search for a particular city that I care about, in
order to find out some information about its airport, like its three letter code.
So here's the first step that I need in order to read in this data
into my program.
I need some way to represent this data.
So we know how to do that.
We know how to write classes and create instances of those classes, so
let's do that.
Let's write a class called Airport.
And it's going to have a field for
each piece of information we wanna represent about a particular airport.
In this case, we'll represent a city, a country, and that three-letter code,
as well as whatever information we want to keep about our airport.
Each of these fields is going to be private.
As I mentioned, a rule of thumb is to keep all of our data private, but
we'll provide getters, so we can access each of those pieces of information.
They'll get set in the constructor when I read in the data from this file.
And then I have access to all of these pieces of information for
each airport that's stored in my program.
So let's imagine that I've done that.
I've written some code that reads in this file that has all this information about
these airports into my Java program by creating
one instance of this airport class for each airport in that file.
I'm gonna simplify things a lot.
And I'm gonna imagine that my entire file only had eight airports in it.
So I'll read those all into,
each into an individual airport object which I'm going to store in an array.
So my array is going to be called airports.
It's an array of references to airport objects.
So one object for each airport.
And what's stored in the array again,
is a reference to this object which you see depicted here in the blue boxes.
And those objects exist somewhere in your computers memory, somewhere in the heap.
And again, what could store in the array is the references to those objects.
But this diagram is a little bit too complicated for my needs for this lesson.
So I'm gonna simplify things a little bit by writing all of the information from
each object directly in the box for the array itself.
So this is going to be my representation of the data that I've now read
into my computers memory from that big airports.dat file.
And again, there's a very simplified version for the purpose of illustration.
So now, I've got all the data about all my airports right into my array and now,
I can write a program to answer questions about the airports in that array.
And in order to answer a question about a particular city's airport,
I have to find that airport object first.
So, let's look at how to do that.