Binary Search

• 01-09-2002
Unregistered
Binary Search
I've been trying to write my own binary search algorithm. I just can't seem to do it. Anyway, I found this source, and, as usual, it doesn't work. Can someone, please, fix this for me?

*Binary Search (<= log2 N steps for array of size N)
*/

#include

int main(){
int arraysize = 10; //so that its easier to change arraysize for testing
int temp = 0;

int L = 0;
int T = 0;
int U = arraysize;
int M = (L+U)/2;

int x[arraysize];

/* Pre-Assertion: It is assumed for this problem that the array of size arraysize has
* been initialized. The values range from 0 to arraysize - 1. L has been assigned to
* the lower bound (0 in this case) and U, the upper bound, has been set to arraysize - 1.
* The array has been sorted into non-decreasing order such that for any i where L <= i < U
* the following holds true: x[i] <= x[i+1].
*/

//I simply used this for-loop to set the values of x[L...U]. It sets the value of x[i]
//to i + 1
for (int i = 0; i < arraysize; )
i = x[i] = i + 1;
//x[i] = temp + i%3 + 1; //Another idea I had for assigning values
//temp += i%3 + 1; i++;

//User input
cout << "\nEnter the value to look for: ";
cin >> T;
//Variables to count the loops and comparisons
int j = 0; int k = 1;

/*Invariant: T is the user-inputted value which if contained in X[0...arraysize-1] must
* also be contained in X[L...U] for some sub-range bounded inclusively by L and U. If
* L becomes larger than U, then the loop breaks.
* In this problem it is assumed that real #'s get rounded down (for instance, 9/2 = 4.)
* It is the case that a comparision is made before the loop gets executed.
*/

//Main Algorithm Code----------//
while(L <= U){
j++; k++;
if ( T > x[M] ) L = M + 1;
if ( T <= x[M] ) U = M - 1;
M = (L+U)/2;
}
//-----------------------------//

/*Post-Assertion: If the value (integer) T exits in array x, it is between U and L and at
*position M such that T = x[M+1]. The thing is, the values have crossed and L is now greater
*than U. So here M = U because M = (U + L) / 2 and now L = U + 1 so it is (U + U + 1) / 2.
*Well (2U + 1)/2 = U + 1/2 and the numbers round down so M is simply U. Because the numbers round
*down, M + 1 = L because U + 1 = L. T is at position x[L] due to the way the loop is setup with
*The check is made to see if x[L] == T after the loop has terminated. The results are output.
*I had the loops and comparisons outputted for testing purposes.
*/
else {
cout << "Value is at position " << L << endl;
cout << "Statistics: " << j << " loops and " << k << " comparisons." << endl;
}
return 0;
}