# Binary search

• 11-20-2011, 06:09 PM
thirdage
Binary search
Hello :)

I'm trying to make an interactive program (guess the number)
the idea is that i put a number in my head and the program tries to guess it.
the program should ask whether the number is less or greater than the middle of the search interval.
the number should be between 1 & 1000.
so what should the psuedo code be ?

Thanks!!
thirdage.
• 11-20-2011, 06:14 PM
Fubarable
Re: Binary search
Quote:

Originally Posted by thirdage
I'm trying to make an interactive program (guess the number)
the idea is that i put a number in my head and the program tries to guess it.
the program should ask whether the number is less or greater than the middle of the search interval.
the number should be between 1 & 1000.

Nice assignment! :)-:

Quote:

so what should the psuedo code be ?
You first! :(nod):

Seriously though, if you don't give it a go first, you'll be cheating yourself out of a tremendous learning opportunity.

Much luck!
• 11-20-2011, 06:58 PM
thirdage
Re: Binary search
I'am just not getting it !!
Code:

``` public class guessNumber {         public static void main(String[] args)         {                 System.out.print("Is your number between 1 and 1000 ?");                 int start=1;                 int end=1000;                 int middle =(((end-start)/2)+start);                 int oldmiddle = 0;                 boolean numfound = false;                 while (!numfound)                 {                         boolean usersAnswer = StdIn.readBoolean();                         if (usersAnswer ==true)                         {                                 ifTrue(middle,start);                                 oldmiddle = (((end -middle)/2)+middle);                                 middle = (((middle-start)/2)+start);                         }                         else                         {                                 ifFalse(oldmiddle,start);                         }                 }         }         public static void ifTrue(int mid,int start)         {                                 System.out.print("is your number less than "+mid+" ?");                                         }         public static void ifFalse(int mid,int start)         {                 System.out.print("is your number less than "+mid+" ?");         } }```
I tried this ... but i can't configure how to set the interval each time!
• 11-20-2011, 07:08 PM
JosAH
Re: Binary search
In a range lo ... hi, you pick an element in the middle: lo ... mid ... hi; if the guess is correct, you're done; otherwise if your guess is too high, pick the interval lo ... mid-1, otherwise pick the interval mid+1 ... hi.

kind regards,

Jos
• 11-20-2011, 07:44 PM
thirdage
Re: Binary search
example :

am picking 40
the program asks if it's between 1 & 1000
between 1 & 500
: true
1&250
:true
//
//
//
1&32
: false
32 & 63
:true
then 47 & 63
:false

I mean each time the interval gets small ... and we ask whether it's between the midpoint of interval and end if false
or start and midpoint if true ... hope you get what I mean.
Thanks again!
• 11-20-2011, 07:47 PM
JosAH
Re: Binary search
Quote:

Originally Posted by thirdage
hope you get what I mean.

Erm, no; sorry.

kind regards,

Jos
• 11-20-2011, 07:51 PM
thirdage
Re: Binary search
If true:
1-1000 becomes [1--500] where we got the midpoint of 1 & 1000.
if false after [1--500] was true:
we check on [500--1000]
then true
we check on [750-1000] .... (where 750 = ((1000-500)/2) +500).
• 11-20-2011, 07:57 PM
JosAH
Re: Binary search
Have you read my reply #4? The boundaries are important you know ...

kind regards,

Jos