Task -- The goal in this code problem is to implement the binary search algorithm.
Input Format -- The first line of the input contains an integer n and a sequence a0 < a1 < ... < an−1 of n pairwise distinct positive integers in increasing order. The next line contains an integer k and k positive integers b0,b1,...,bk−1.
Constraints -- 1 ≤ n,k ≤ 10^4; 1 ≤ a[i] ≤ 10^9 for all 0 ≤ i < n; 1 ≤ b[]j ≤ 10^9 for all 0 ≤ j < k;
Output Format -- For all i from 0 to k−1, output an index 0 ≤ j ≤ n−1 such that aj = bi or −1 if there is no such index.
I am using code blocks with c++11 compiler. I have already tried stress testing and got correct results in my system. But coursera autograder is giving me unknown signal 11. In some problems it gives unknown signal 8. Can anyone tell me the possible reason behind this.
int binary_search(const vector<long long> &a, long long x) {
size_t left = 0, right = (size_t)a.size()-1;
size_t mid = 0;
while(left<=right){
mid = (left+right)/2;
if(x < a[mid]){
right = mid-1;
}
else if(x > a[mid]){
left = mid+1;
}
else return mid;
}
return -1;
}
int main() {
size_t n;
std::cin >> n;
vector<long long> a(n);
for (size_t i = 0; i < a.size(); i++) {
std::cin >> a[i];
}
size_t m;
std::cin >> m;
vector<long long> b(m);
for (size_t i = 0; i < m; ++i) {
std::cin >> b[i];
}
for (size_t i = 0; i < m; ++i) {
//replace with the call to binary_search when implemented
std::cout << binary_search(a, b[i]) << ' ';
}
}
Actual result that i got in autograder.
Failed case #4/36: unknown signal 11 (Time used: 0.00/1.00, memory used: 40071168/536870912.)
If the vector has e.g. size 2, then you initialize left = 0, right = 1 and mid = 0. left <= right so you calculate mid = 0 and check if x < a[0]. If that happens, you now set right = -1. In unsigned arithmetic, that is a really large number. Your loop continues because 0 <= really large number, you calculate mid = half of really large number and access the vector there. That's UB and gets your program killed.
Switching to signed types means right = -1 is indeed smaller than left = 0 and terminates the loop.