I'm in problem set 3. Maybe I missed something, but I didn't hear exactly *how* to do bisection search! I tried looking it up online but I just got a lot of algorithmic gibberish I'm sure makes perfect sense to smart people. Anybody got an easier explanation?

Question

anonymous · Answer

A bisection search is used to converge on an answer that means each time we guess, we get closer to the correct answer. You need to know a min possible answer and a max possible answer.
Let's say I ask you to guess the number 'm thinking of which is between 1 and 100, inclusively, and let's say I only need you to be accurate within +/- 5.
I pick 36, but you don't know this.
You guess (high + low)/2 = (100+1)/2  which is about 50
I say lower.
High = 49
Low = 1
You guess (high + low)/2 = (49 + 1)/2 = 25
I say higher.
High = 49
Low = 26
You guess (high + low)/2 = (49 + 26)/2 = 75/2 = 37
I say you're within 5! You win!
That's how bisection search works.

anonymous · Answer

Thanks! :) that helps a lot!

anonymous · Answer

it wasn't covered in the lecture? http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/video-lectures/lecture-6/

anonymous · Answer

Not that I heard, and I got a whole page of notes. I don't think I missed anything.

anonymous · Answer

Wait, that's lecture 6, and this was in the problem set for lecture 3. Is it somehow out of order?

anonymous · Answer

i posted the link to the 2008 course lecture that covers bisection (i think) - watch it.