
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_STUDENT1);
cout<<" \n\t Enter the student number to search :";
cin>>key;
k=binarySearch(record, 0, N_STUDENT1, key);
if(k>=0)
cout<<"Student Details with student Number "<<key<<"exists at the position "<<k;
else
cout<<"Not found ";
}

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.

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.