Loading...

Linear Search

Course video 30 of 60

In this module you will learn about a powerful algorithmic technique called Divide and Conquer. Based on this technique, you will see how to search huge databases millions of times faster than using naïve linear search. You will even learn that the standard way to multiply numbers (that you learned in the grade school) is far from the being the fastest! We will then apply the divide-and-conquer technique to design two efficient algorithms (merge sort and quick sort) for sorting huge lists, a problem that finds many applications in practice. Finally, we will show that these two algorithms are optimal, that is, no algorithm can sort faster!

Algorithmic Toolbox

カリフォルニア大学サンディエゴ校

データ構造とアルゴリズム専門講座における 6 の 1 コース

The course covers basic algorithmic techniques and ideas for computational problems arising frequently in practical applications: sorting and searching, divide and conquer, greedy algorithms, dynamic programming. We will learn a lot of theory: how to sort data and how it helps for searching; how to break a large problem into pieces and solve them recursively; when it makes sense to proceed greedily; how dynamic programming is used in genomic studies. You will practice solving computational problems, designing new algorithms, and implementing solutions efficiently (so that they run in less than a second).

シラバスを表示

学習するスキル

Dynamic Programming, Debugging, Software Testing, Algorithms, Computer Programming

講師

Alexander S. Kulikov
Visiting Professor
Michael Levin
Lecturer
Neil Rhodes
Adjunct Faculty
Pavel Pevzner
Professor
Daniel M Kane
Assistant Professor

字幕

We're going to start our divide and conquer algorithms

with what might be considered a degenerate form of divide and conquer:

Searching in an unsorted array using linear search.

Here's an example of an array.

To find a particular element of the array,

we look at the first element, if it's not there, we look at the second element.

We continue until we either find the element we're interested in, or

until we reach the end of the array.

This same type of search is also used to free elements that are stored

in a linked list.

Let me describe a real-life use of linear search.

Twenty years ago I did consulting for a company developing software for

one the first hand-held computers, the Apple Newton.

The application translated words between any two of the languages:

English, French, Italian, German, or Spanish.

Its data was stored in five parallel arrays.

So for example, car was in English at the second position.

In Spanish, car is auto, so

the second position of the Spanish array contained auto.

The program would take the user's input word along with from and to languages.

Then it would search through the corresponding from array, English for

example with trying to translate car from English to Spanish.

If it found a match,

it returned the element at the same index location and target language.

With a small dictionary of three words, as in this example,

this linear search is quick.

However, I was brought in as a consultant to speed up the application.

When users clicked on the translate button, it'd take seven to ten seconds

to retrieve the translated word, an eternity as far as the user was concerned.

There were about 50,000 words in the dictionary, so

on average it took 25,000 word checks in order to find a match.

The next video, I'll show you how we sped up this application using binary search.

The problem statement for linear search is as follows:

given an unsorted array with n elements in it and a key k, find an index,

i of the array element that's equal to k.

If no element array is equal to k, the output should be NOT_FOUND.

Note that we say an index rather than the index, to account for

the fact that there may be duplicates in the array.

This might seem pedantic, but it's important

to be as careful as possible in specifying our problem statement.

The well known solution to this problem is a linear search.

Iterate through the array until you find the chosen element. If you reach

the end of the array and haven't yet found the element, return NOT_FOUND.

We can construct a divide and conquer recursive algorithm to solve this problem.

Our recursive function will take four parameters:

A, the array of values;

low, the lower bound of the array in which to search;

hgh, the upper bound of the array in which to search; and k,

the key for which to search.

It will return either: an index in the range low to high,

if it finds a matching value; or NOT_FOUND, if it finds no such match.

As with all recursive solutions, we'll need to accurately handle the base case.

In particular, base cases for this problem will be either: be given an empty array, or

finding a match on the first element.

The subproblem is to search through

the sub array constructed by skipping the first element.

We'll recursively search through that smaller sub array,

and then just return the result of the recursive search.

Although this is a recursive routine that breaks the problem into

smaller problems,

some would argue that this shouldn't be called divide and conquer.

They claim that a divide and

conquer algorithm should divide the problem into a smaller subproblem,

where the smaller subproblem is some constant fraction of the original problem.

In this case the su-problem isn't 50%, or 80%, or

even 95% of the original problem size.

Instead, it's just one smaller than the original problem size.

I don't know, maybe we should call this algorithm

subtract and conquer rather than divide and conquer.

In order to examine the runtime of our recursive algorithm it's often useful to

define the time that the algorithm takes in the form of a recurrence relation.

A recurrence relation defines a sequence of values in terms of a recursive formula.

The example here shows the recursive definition of the values

in the Fibonacci sequence.

You can see that we defined the value for

the n'th Fibonacci as the sum of the preceding two values.

As with any recursive definition, we need one or more base cases.

Here, we define base cases when evaluating F(0) and F(1).

From this recursive definition, we've defined values for evaluating F(n) for

any non-negative integer, n.

The sequence starts with 0, 1, 1, 2, 3, 5, 8, and continues on.

When we're doing run-time analysis for divide and conquer algorithms,

we usually define a recurrence relation for T(n).

where T stands for the worst time taken for the algorithm, and

n is the size of the problem.

For this algorithm, the worst-case time is when an element isn't found

because we must check every element of the array.

In this case we have a recursion for a problem of size n

which consists of a subproblem of size n minus one plus a constant amount of work.

The constant amount of work includes checking high versus low,

checking A at low equals key, preparing the parameters for the recursive call,

and then returning the result of that call.

Thus the recurrence is T(n) equals T(n-1) plus c,

where c is some constant.

The base case of the recursion is in an empty array, there's a constant amount of work:

checking high less than low and then returning NOT_FOUND.

Thus T(0) equals c.

Let's look at a recursion tree in order to determine how

much total time the algorithm takes.

As is normal, we're looking at worst-case runtime,

which will occur when no matching element is found.

In a recursion tree, we show the problem along with the size of the problem.

We see that we have an original problem of size n which then generates a subproblem

of size n-1, and so on all the way down to a subproblem of size zero:

an empty array. The work column shows the amount of work that is done at each level.

We have a constant amount of work at each level which we represent by c, a constant.

Alternatively, we could have represented this constant amount of work

with big theta of one.

The total work is just the sum of the work done at each level

that's a summation from zero to n of a constant c.

Which is n plus one times c, or just big theta of n.

This analysis seems overly complicated for such a simple result.

We already know that searching through n elements of the array will take big theta of n time.

However, this method of recurrence analysis will become more useful

as we analyze more complicated divide and conquer algorithms.

Many times a recursive algorithm is translated into an iterative one.

Here we've done that for the linear search.

We search through the elements of array A from index low to index high.

If we find a match, we return the associated index.

If not, we return NOT_FOUND.

To summarize, what we've done is one: created a recursive solution;

two: defined a corresponding recurrence relation, T;

three: solved T of n to determine the worst-case runtime; and

four: created an iterative solution from the recursive one.

What you've seen in this video, then, is an example

of a trivial use of our divide and conquer technique in order to do a linear search.

In our next video we'll look at a non-trivial use

of the divide an conquer technique for searching in a sorted array:

the well known binary search.

Courseraについて

コース、専門分野と世界最高の大学や教育機関からのトップ講師が教えるオンライン学位。

Join a community of 40 million learners from around the world

Earn a skill-based course certificate to apply your knowledge

Gain confidence in your skills and further your career

コーセラは、世界トップクラスの教育を世界中に配信しています。最高峰の大学や組織とのパートナーシップに基づくオンラインコースが提供されています。

© 2019 Coursera (株)すべての権利予約します。

App Storeからダウンロード

Google Playで取得