Hello, I'm solving this problem: spoj.com/problems/BSEARCH1/
This is my code (it includes optimization because without optimization the program excedeed time limit):
ideone.com/0CSrEj
I need a test case that will help to find a mistake. I've tried several cases and can't find mistakes.
Mar '13
Mar '13
Your binary search algorithm is a little confusing. What is the purpose of arr_to_k?
Your algorithm is also slow. In the worst case it is O(n). Think about the case where all elements in the array are the same.
The idea of optimization is to divide the original array into several pieces of the same size and make an auxilary array out of the first elements of these pieces.
For example, if original array is 2 4 7 7 9, the auxilary array will be 2 7 9.
when we look for the index of the query element, first we look it up in the auxilary array. The query element won't necessarily be there, but the auxilary array can show us upper bound and lower bound from which we should start binary search in the original array.
arr_to_k is a flag for cases when the query element is not in the auxilary array. Let me show what's it for using the following example. Let the query element be 4.
Step 1. We look at the auxilary_array. 7>4. We have to go left. arr_to_k = 2
Step 2. We look at the auxilary array. 2<4. We have to go right. If arr_to_k wasn't 1, we would return to 7 and then keep cycling between 2 and 7 in the auxilary array. But the value of arr_to_k says that we have to stop and look for k in the original array, somewhere between the original positions of 2 and 7.
Without this optimization the program coudn't pass time limit. Now it passes it. This optimization is helpful when the size of the array being searched through is big.
Why do you rebuild the auxiliary array for every q? One would think that the auxiliary array wouldn't change each from q to q? Why not build the auxiliary array when reading the input? That way bsearch would only need this array.
