Search in Rotated Sorted Array

Question

Problem statement:

There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2]. Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums. You must write an algorithm with O(log n) runtime complexity.

I have written the exact similar code given in submissions for the problem, but, it fails for one of my output. I am unable to find the reason. Am I missing some logic?

class Solution {
    public int search(int[] nums, int target) {
        int left = nums[0];
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (target == nums[mid]) {
                return mid;
            } else {
                // if left sorted
                if (nums[left] <= nums[mid]) {
                    if (nums[left] <= target && target < nums[mid]) {
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                } else {
                    // else right sorted
                    if (nums[mid] < target && target <= nums[right]) {
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
            }
        }
        return -1;
    }
}

The code fails to provide output for nums = [6,7,1,2,3,4,5] and target = 7.

Expected output is 1, actual output is -1.

Answer 1

Disgusting mistake, we usually don't look at simple initialization twice ;) and I've been going through main algo body first. But debugging would help.

Replace

int left = nums[0];

with

int left = 0;