Thread: Binary Search

  1. #1
    Registered User
    Join Date
    Apr 2011
    Posts
    12

    Binary Search

    I have a Program that I'm using Binary Search.
    Which is Working with Merge_Sort.

    But what i can't figure out, is how to Try Catch the Binary Search
    To see if the User. Sorted the array before using Binary Search.
    If they Didn't sort the Array then they should not be allowed to use Binary Search

    Code:
    //function binary search using the key value to serach 
    int binarySearch(student  sorted[], int first, int upto, int key) {
        
        while (first < upto) {
            int mid = (first + upto) / 2;  // Compute mid point.
            if (key<sorted[mid].student_number)
            {
                upto = mid;     // repeat search in bottom half.
            } else if (key>sorted[mid].student_number) 
            {
                first = mid + 1;  // Repeat search in top half.
            } else 
            {
                return mid;     // Found it. return position
            }
        }
        return -(first + 1);    // Failed to find key
    }
    Code:
     {
                merge_sort(0,N_STUDENT-1);
                cout<<" \n\t Enter the student number to search :";
                cin>>key;
                k=binarySearch(record, 0, N_STUDENT-1, key); 
                if(k>=0)
                    cout<<"Student Details with student Number "<<key<<"exists at the position "<<k;
    			else
    				cout<<"Not found ";
    		}

  2. #2
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Location
    CA, USA
    Posts
    466
    Well, the only way to see if a given sequence is sorted is to go through it element by element, which takes O(n) time, where n is the length of the sequence.

    Binary search is log2(n), but if you test the sequence to prove its sorted, then it becomes a slow log2(n^2), which is not what people expect from a binary search.

    EDIT: actually that's not correct. But validating will still take an extra O(n) time for every search.

    A better way is to assume your sequence is sorted by stating something like:

    Precondition of binary_search(array) is that array is sorted in ascending order. Then in the name of efficiency, you can trust your users know what they are doing.
    Last edited by MacNilly; 04-07-2011 at 04:26 PM.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Generally you have no choice but to know beforehand if the array is sorted. If you cannot be 100% sure then you cannot be sure that a binary search will work. Despite what I'm writing below, I'd like to get across that this is my main point.

    However, there is one circumstance where you can take advantage of a binary search on an array that is not known to be always sorted. That case is where you know for certain that the item you are searching for is in the array. I call it a "Hopeful Search" and you can find more about it here.
    Basically, if the binary search fails then it searches amoung the remaining unvisited items, still perferring to take advantage of whatever sortedness does happen to be there. As long as it is largely or at least partially sorted, then it can still provide approximately O(log n) amortised search time, or close to it.
    Worst case is if the item is not actually present in the array, in which case it is O(n) but with a higher constant factor that a sequential search.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

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, 06: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