Not all programs are created equal. Â In this course, we'll focus on writing quality code that runs correctly and efficiently. Â We'll design, code and validate our programs and learn how to compare programs that are addressing the same task.

Loading...

From the course by University of Toronto

Learn to Program: Crafting Quality Code

276 ratings

Not all programs are created equal. Â In this course, we'll focus on writing quality code that runs correctly and efficiently. Â We'll design, code and validate our programs and learn how to compare programs that are addressing the same task.

From the lesson

Week 3

- Jennifer CampbellAssociate Professor, Teaching Stream

Department of Computer Science - Paul GriesAssociate Professor, Teaching Stream

Department of Computer Science

Linear search searches for a value on a list starting at index zero.

Â It proceeds linearly through the list until it finds the value.

Â If there are n items in the list, then linear search might look at all n items.

Â For example, if the value is not in the list, then it will examine each item in

Â the list. Linear search works on both sorted and

Â unsorted lists. However, if we know that the list is

Â sorted, we can do much, much better using an algorithm known as binary search.

Â Here is the function header and box string for binary search.

Â Like with linear search, it takes a list and a value and returns the index of the

Â first occurrence of that value in the list, or minus 1 if the value is not in

Â the list. Binary search only works if L is sorted.

Â It turns out that it also only works if each item in L can be compared to v.

Â Here's an example to get you used to the idea.

Â Here, we have a sorted list of numbers and we're searching for 5.

Â We want the first occurrence of 5, the 1 at index 3.

Â Let's draw a dividing line. This line divides the items that are less

Â than v from the items that are bigger or equal to v.

Â Notice that this includes the item in index 3, the 5 that we're looking for.

Â Let's say, we have a list of 100,000 items.

Â We can calculate the middle index pretty easily and we can examine that value.

Â If that middle value is less than the value we're looking for, then because the

Â list is sorted, we know that all of the values to the left of it are also less

Â than the value we're looking for. And therefore, we can eliminate 50,000

Â items with just one comparison. So, partway through our binary search

Â algorithm, we have three regions in our list.

Â On the left are all the items that are less than v, on the right are all the

Â items that are greater than or equal to v.

Â And in the middle is the unknown section, the items we know nothing about yet.

Â Let's mark the beginning of that unknown section with a variable b and the end of

Â that unknown section with a variable e. When this function is called, we know

Â nothing about any of the values in the list.

Â And so, b will start off at index zero and e will start off at index length of L

Â minus 1. Here's the code.

Â At the end of this process, the unknown section is empty.

Â Everything on the left is less than v, everything on the right is greater than

Â or equal to v. The unknown section is empty.

Â Variable b is to the right of the line, and variable e is to the left of the

Â line. This is what it looks like in the

Â beginning. And this is what it looks like at the

Â end. So, this loop is going to continually

Â march b and e closer to eachother until they cross.

Â In our loop, we'll calculate the midpoint between b and e, then we'll examine it to

Â see if that item is less than v. If it is, we can set i's new value to m

Â plus 1 because all these values are less than v.

Â On the other hand, if the item in index m is grater or equal to v, then we can move

Â e to m minus 1 because all the v's values are grater than or equal to v.

Â Let's write our loop. We'll figure out the loop condition in a

Â moment. But if the item in index is less than v,

Â then we'll going to move b to index n plus 1.

Â And if the item in index 1 is greater than or equal to v, then we'll move i to

Â index n minus 1. And now for the loop condition, in the

Â end, b is greater than e. We continue then as long as b is less

Â than or equal to e, because there are still items in the unknown section.

Â And here's the condition. All that's left is to calculate the value

Â for m. We take the average of two numbers like

Â this. But because we don't want a floating

Â point number, we need to do integer division.

Â This code produces this. But we're not quite done.

Â What if this value isn't v? Well, in that case, we are supposed to

Â return minus 1. We have to be a little bit careful here

Â because all of the values might be greater than or equal to v, or they might

Â all be less than v. If they're all greater than or equal to

Â v, then this section here takes up the entire list.

Â b is on the right, e is on the left, b must be zero.

Â We can look at L [UNKNOWN] zero, that's fine.

Â But, what if they're all less than v? Then, this line ends up over on the right

Â because this whole section takes up the whole list.

Â And in that case, b ends up here, and e ends up there.

Â b is now the length of L and I can't use that as an index.

Â I'll get an index error. I'm going to write a new statement.

Â In one situation, I'm going to return minus 1.

Â That's when v is not in the list. Otherwise, I'm going to return index b.

Â Because if v is on the list, b is going to be the index of the first occurrence

Â of v. I know that one situation where v is now

Â the lowest can be detected by comparing b to length of L.

Â So, if b is the length of L, I want to return minus 1.

Â Or if L at index b is not equal to v, then I also want to return minus 1.

Â If b isn't the length of L, and L at b is equal to v, I want to return index b.

Â Let's write some doc test code. If this module is the one being run, then

Â we'll import doctest, and we'll run our tests.

Â Keep your fingers crossed. And we win.

Â Coursera provides universal access to the worldâ€™s best education,
partnering with top universities and organizations to offer courses online.