# Runtime Error on OJ but running correct locally??

• Hi,

my solution runs fine on my Visual Studio 2013 but keeps seeing runtime error on OJ.
I'm testing exactly the same test case that OJ is complaining about.
not sure if anyone had this issue before??

The implementation is basically using binary search to find the pivot, and then use another basic binary search to find the target. hope it's easy to read:

``````class Solution {
public:
int search(int input[], int n, int target) {
A = input;
int pivotIdx = findPivotIdx(0, n);

if (pivotIdx == -1){
// a normal sorted array
return binarySearch(0, n, target);
}
else if (A[pivotIdx] == target){
return pivotIdx;
}
else{
// A[pivotIdx] is the smallest
if ((target > A[n - 1]) && (target <= A[pivotIdx - 1])){
// in first part
return binarySearch(0, pivotIdx, target);
}
else if ((target > A[pivotIdx]) && (target <= A[n - 1])){
// in second part
return binarySearch(pivotIdx + 1, n - 1 - pivotIdx, target);
}
else{
return -1;
}
}
}
int* A = NULL;
int findPivotIdx(int startIdx, int size){
// let the pivot to be the true smallest element
if (size <= 1){
return -1;
}
else if (size == 2){
if (A[startIdx] > A[startIdx + 1]){
return startIdx + 1;
}
else{
return -1;
}
}
else{
// more than 2 elements
if (A[startIdx + 1] < A[startIdx]){
return startIdx + 1;
}
else if (A[startIdx + size - 1] < A[startIdx + size - 2]){
return startIdx + size - 1;
}
}

// recursive
int middleIdx = startIdx + (size >> 1);
if ((A[middleIdx] < A[startIdx + size - 1]) && (A[startIdx + size - 1] < A[startIdx])){
// middle idx is the pivot
return middleIdx;
}
else if (A[middleIdx] > A[middleIdx + 1]){
return middleIdx + 1;
}
else if ((A[startIdx] > A[middleIdx]) && (A[middleIdx] > A[startIdx + size - 1])){
// pivot is in the left, startIdx,...., (middleIdx - 1)
return findPivotIdx(startIdx, middleIdx - startIdx);
}
else{
// A[size - 1] > A[middleIdx] > A[startIdx]
// pivot is in the right, (middleIdx + 1),...., (size - 1)
return findPivotIdx(middleIdx + 1, size - 1 - middleIdx);
}

}

int binarySearch(int startIdx, int size, int target){
// base cases
if (size == 0){
return -1;
}
else if (size == 1){
if (target == A[startIdx]){
return startIdx;
}
else{
return -1;
}
}
else{
// size >= 2
if (target == A[startIdx]){
// first element
return startIdx;
}
else if (target == A[startIdx + size - 1]){
// last element
return startIdx + size - 1;
}
else if ((target < A[startIdx]) || (target > A[startIdx + size - 1])){
// out of range
return -1;
}
}

// recursive
int middleIdx = startIdx + (size >> 1);
if (target == A[middleIdx]){
return middleIdx;
}
else if (target > A[middleIdx]){
return binarySearch(middleIdx + 1, size - 1 - middleIdx, target);
}
else{
// target < A[middleIdx]
return binarySearch(startIdx, middleIdx - startIdx, target);
}

}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.