+1

JumpSearch + BinarySearch, some help

pastebin code(C++): https://pastebin.com/tTpJ4Ni0 #include <iostream> #include <cmath> using namespace std; int JumpSearch(int x); int BinarySearch(int x, int left, int right); int V[] = {1,2,3,4,5,6,7,8,9,10}; int main() { cout << JumpSearch(8); return 0; } int JumpSearch(int x) { int left = 0; int right = sqrt(10); while (left < right){ if (V[right] == x) return right; if (V[right] > x) return BinarySearch(x,left,right); if (V[right] < x) left = right; right = right * 2; } } int BinarySearch(int x, int left, int right) { if (left < right){ int mid = (left + right) /2; if (V[mid] == x) return mid; if (V[mid] >x) right = mid - 1; if (V[mid] < x) left = mid +1; } return -1; } i always get -1 as a result, no matter what number i put in to search, some help, im stucked :/

4/1/2020 10:30:41 AM

Lyrdum

2 Answers

New Answer

+1

You multiply the index “right” by 2, without checking it on out of array bounds. Outside the array there is only garbage which of course is not ordered. These algorithms work only on ordered arrays. You should check index "right" on array size exceeding like this: int JumpSearch(int x) { constexpr int size = sizeof(V)/sizeof(V[0]); int left = 0; int right = sqrt(size); while (left < right){ if (V[right] == x) return right; if (V[right] > x) return BinarySearch(x,left,right); if (V[right] < x) left = right; right = right * 2; if(right >= size) right = size - 1; } return -1; } Also your JumpSearch() function didn't have a return statament at the end of the definition.

+1

@andriy kan, I did that before but i was so dumb that i put size = sizeof(V[0]) / sizeof(V) instead of v / v[0] and i was getting every time 0 as output, i struggled with this stupid bug almost 2 hours after repetitive modification on the code