The Internet belongs to everyone. Let’s keep it that way.

Protect Net Neutrality
Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present 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

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Binary Search

Visual of a short binary search.
by

Sam Whay

on 13 April 2010

Comments (0)

Please log in to add your comment.

Report abuse

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 transcript