Can we use Binary Search Template II for "Search in Rotated Sorted Array"?
Brian
505
Binary Searchexplore

I tried to use Binary Search Template II for "Search in Rotated Sorted Array" and I got heap over flow from OJ.
However, it works (or passes OJ at least) when I set right as length - 1.

Am I doing something wrong here?

    int left = 0, right = nums.size() -1;
	while ( left < right ) {
        int mid = left + ( right - left ) / 2;
        if ( target == nums[mid] ) return mid;
        else if ( nums[mid] < nums[right] ) {
            if ( nums[mid] < target && target <= nums[right] ) {
                left = mid + 1;
            } else {
                right = mid;
            }
        } else {
            if ( nums[left] <= target && target < nums[mid] ) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
    }
Comments (2)