### Present Remotely

Send the link below via email or IM

CopyPresent to your audience

Start remote presentation- Invited audience members
**will follow you**as you navigate and present - People invited to a presentation
**do not need a Prezi account** - This link expires
**10 minutes**after you close the presentation - A maximum of
**30 users**can follow your presentation - Learn more about this feature in our knowledge base article

# Binary Search

Visual of a short binary search.

#### Transcript of Binary Search

Double click anywhere & add an idea What's a binary search? It's a common search algorithm

used to find a number in a presorted list. BUT WHAT DOES IT ALL

MEAN?! Well, we're going to show

you...using pictures. Exhibit A: The Sorted List 0 1 2 3 4 Each box, or "element" is numbered.

Computer scientists start counting at zero

because we like to be weird.

These numbers are pretty important in order to

do a binary search. Now we have to do some math.

Don't worry, it's not hard.

In order to find the middle element, add

the number of the first and last element and then

simply divide by two. For our search, this is pretty easy.

(0+4)/2=2 Things get more interesting when you've got an odd

number to divide by two. You need to have an integer,

because you're going to look in the box that has the number

that you just found.

For example, if you have (0+5)/2, you'd normally say that it's 2.5,

but you can't do that here. You can't look in the "reddish purple" box,

you have to look in the red box OR the purple box.

Therefore, you'd round down. When you're doing integer division, 5/2 is

actually 2. Ooops, I almost forgot something very

important! We have to determine what number

we want to search for in the set of boxes.

Let's say that we want to find 5, located in the yellow

box. The reason the list has to be sorted is that

you're going to compare the number that you

want to find to the middle element. If it's equal to the middle, you've found

what you're looking for and you can stop. Since the list is sorted, you know the five

isn't thrown over with the one and the two.

There's no reason to look over there.

If the list isn't sorted, though, there's no way

of knowing where the five could possibly be, and

a binary search won't work. Five isn't equal to three and it's bigger

than three, so we're going to look over on

the right side from now on. (insert grotesque chopping, screaming, splattering noises here) While the rest of the list is still technically

there, we aren't using it and we're going

to pretend like it got chopped off. (Plus, it's annoying to resize those

boxes each time.) Here's the new set of numbers. 3 4 They're still numbered the same. Remember that the rest of the list

is still there. It's just...hiding. Now we have to do what we

did all over again. The "middle" number is...

(3+4)/2=3 Remember integer division? 3 4 The number in box 3 isn't five, so I guess

we have to try again...

(Hooray!) Now there's only one box left, box four

which contains the five. Well, it's the last box, so we know the number's

there, right? WRONG! What if I decided I wanted to look for 6? 29? 138? -5? None of those are in there, but I could still search for them if I wanted. You and I know that five is in the last box. We're humans. We're smart. Computers are dumb. Your computer doesn't know what's in that box, and it can't until it checks. So let's check! 4 Aw, more math? You'll live. There's only one box left, so it's both the first and the last box. (4+4)/2=4 Let's look in box 4.

(Ohh the suspense! What will we find?!) 4 IT'S FIVE! Now the computer can tell you, "Oh, hey, I found your

number. It was in box 4." And you've successfully binary searched! Wanna see it in C++? while (first<=last) {

mid=(first + last)/2;

if (key>sortedArray[mid]){

first=mid + 1;

//the number of the middle box was smaller than

//were looking for, so the first box number

//changes

}

else if (key < sortedArray[mid]){

last = mid - 1;

//the number of the middle boxwas bigger than what

//you were looking for, so the last box number

//changes

}

else{

return mid;

//the computer tells you what box it found

//the number in

}

}

return -(first + 1);

//or else the computer tells you it didn't find

//what you were looking for

Full transcriptused to find a number in a presorted list. BUT WHAT DOES IT ALL

MEAN?! Well, we're going to show

you...using pictures. Exhibit A: The Sorted List 0 1 2 3 4 Each box, or "element" is numbered.

Computer scientists start counting at zero

because we like to be weird.

These numbers are pretty important in order to

do a binary search. Now we have to do some math.

Don't worry, it's not hard.

In order to find the middle element, add

the number of the first and last element and then

simply divide by two. For our search, this is pretty easy.

(0+4)/2=2 Things get more interesting when you've got an odd

number to divide by two. You need to have an integer,

because you're going to look in the box that has the number

that you just found.

For example, if you have (0+5)/2, you'd normally say that it's 2.5,

but you can't do that here. You can't look in the "reddish purple" box,

you have to look in the red box OR the purple box.

Therefore, you'd round down. When you're doing integer division, 5/2 is

actually 2. Ooops, I almost forgot something very

important! We have to determine what number

we want to search for in the set of boxes.

Let's say that we want to find 5, located in the yellow

box. The reason the list has to be sorted is that

you're going to compare the number that you

want to find to the middle element. If it's equal to the middle, you've found

what you're looking for and you can stop. Since the list is sorted, you know the five

isn't thrown over with the one and the two.

There's no reason to look over there.

If the list isn't sorted, though, there's no way

of knowing where the five could possibly be, and

a binary search won't work. Five isn't equal to three and it's bigger

than three, so we're going to look over on

the right side from now on. (insert grotesque chopping, screaming, splattering noises here) While the rest of the list is still technically

there, we aren't using it and we're going

to pretend like it got chopped off. (Plus, it's annoying to resize those

boxes each time.) Here's the new set of numbers. 3 4 They're still numbered the same. Remember that the rest of the list

is still there. It's just...hiding. Now we have to do what we

did all over again. The "middle" number is...

(3+4)/2=3 Remember integer division? 3 4 The number in box 3 isn't five, so I guess

we have to try again...

(Hooray!) Now there's only one box left, box four

which contains the five. Well, it's the last box, so we know the number's

there, right? WRONG! What if I decided I wanted to look for 6? 29? 138? -5? None of those are in there, but I could still search for them if I wanted. You and I know that five is in the last box. We're humans. We're smart. Computers are dumb. Your computer doesn't know what's in that box, and it can't until it checks. So let's check! 4 Aw, more math? You'll live. There's only one box left, so it's both the first and the last box. (4+4)/2=4 Let's look in box 4.

(Ohh the suspense! What will we find?!) 4 IT'S FIVE! Now the computer can tell you, "Oh, hey, I found your

number. It was in box 4." And you've successfully binary searched! Wanna see it in C++? while (first<=last) {

mid=(first + last)/2;

if (key>sortedArray[mid]){

first=mid + 1;

//the number of the middle box was smaller than

//were looking for, so the first box number

//changes

}

else if (key < sortedArray[mid]){

last = mid - 1;

//the number of the middle boxwas bigger than what

//you were looking for, so the last box number

//changes

}

else{

return mid;

//the computer tells you what box it found

//the number in

}

}

return -(first + 1);

//or else the computer tells you it didn't find

//what you were looking for