Binary Search

This is a discussion on Binary Search within the C++ Programming forums, part of the General Programming Boards category; I've been trying to write my own binary search algorithm. I just can't seem to do it. Anyway, I found ...

  1. #1
    Unregistered
    Guest

    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 equals sign in the if statement with U.
    *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.
    */
    if (x[L] != T) cout << "Value not found!" << endl;
    else {
    cout << "Value is at position " << L << endl;
    cout << "Statistics: " << j << " loops and " << k << " comparisons." << endl;
    }
    return 0;
    }


    thank you for your help.

  2. #2
    Registered User
    Join Date
    Dec 2001
    Posts
    194
    instead of int arraysize = 10; inside your main, put #define arraysize 10
    outside main

  3. #3
    ¡Amo fútbol!
    Join Date
    Dec 2001
    Posts
    2,136
    int U = arraysize;

    //and U, the upper bound, has been set to arraysize - 1.


    has it??

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 05:15 PM
  2. deleting all nodes of a binary search tree...
    By sachitha in forum C++ Programming
    Replies: 3
    Last Post: 09-29-2004, 07:19 AM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21