CODEWITHSUNDEEP
data-structuresbinary-searchrecursive-datastructures
Priyanka
Priyanka

Reputation: 333

Binary search for array containing negative values

function BinarySearch(items, value) {
    var start = 0,
    stop = items.length - 1,
    mid = Math.floor((stop + start) / 2);

    while (items[mid] !== value && start < stop) {
        if (value < items[mid]) {
           stop = mid - 1;
        } else if (value > items[mid]) {
           start = mid + 1;
        }
       mid = Math.floor((stop + start) / 2);
    }
    var output = (items[mid] != value) ? -1 : mid;
    return output;
}

var arr = [5, 6, 7, 8, 9, 10, 1, -1, 2, 3];
var key = -1;
var ans = BinarySearch(arr, key);
console.log("ans is " + ans);

I am trying to find - 1, using binary search but it gives incorrect result.This works fine if all array elements are positive but in case array element contains element value and we try to find negative value,it gives incorrect result.

Upvotes: 1

Views: 3397

Answers (1)

1010_Sayantan Sen
1010_Sayantan Sen

Reputation: 21

Binary Search works in logarithmic time. O(log n) This property is satisfied because Binary Search only works on Sorted Array (and the shift conditions varies based on asc and desc order). Your input array is not sorted .

Upvotes: 0

Related Questions