- #1

evinda

Gold Member

MHB

- 3,836

- 0

I want to write an optimal algorithm that solves the following problem:

Someone chooses a number from the set $\{ 1, \dots,1000\}$ and I have to find it. I can ask if the number that was chosen is $< , > , \leq $ or $ \geq $ from a number and the possible answers are yes or no.

Also I want to show that my algorithm is optimal.

I have written the following algorithm:

Code:

```
Algorithm {
int low=1, high=1000;
k=Search(low,high);
printf("The number that was chosen is %d", &k);
return;
}
```

Code:

```
Search(low,high){
char ans;
if (high<low) return 0;
int mid=low+floor((high-low)/2);
printf("Is the number equal to %d ?", &mid);
scanf("%c",&ans);
if (ans=='yes') return mid;
else {
printf("Is the number <= %d", &mid);
scanf("%c",&ans);
if (ans=='yes') Search(low,mid-1);
else Search(mid+1,high);
}
}
```