Leetcode 33. Search in Rotated Sorted Array – Binary search

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.

有一個遞增的Number陣列，裡面的值不會重複。

此陣列在成為參數前，會先被不特定的樞紐k給翻轉。（1 <= k < nums.length）

所以最終傳進的參數會是[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed).

[0,1,2,4,5,6,7] 如果配上參數k，則會變成 [4,5,6,7,0,1,2].

最終要回傳targer在陣列的參數位置。

#這題必須使用O(log n)完成

提到log n 以及有序或部分有序，我們先想到binary search。想辦法捨棄一半的數據

1. 為了做Binary Search，我們先定義right跟left。
2. 準備一個迴圈，設定left <= right 才運作
3. 找出中間值，如果中間值為target則return
4. 如果左邊是有序的，判斷target是否在此range裡面，假如是，right改成mid – 1。假如不是，left改成mid + 1
5. 如果右邊是有序的，判斷target是否在此range裡面，假如是，right改成mid – 1。假如不是，left改成mid + 1
6. 如果都沒有在裡面，return -1

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let left = 0;
    let right = nums.length-1;
    
    while(left <= right){
        let mid = Math.floor((left + right)/2);
        if(nums[mid] == target){
            return mid
        }
        
        // left sorted
        if(nums[left] <= nums[mid]){
            // target not in left
            if(target < nums[left] || target > nums[mid]){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }else{
            // target not in right
            if(target > nums[right] || target < nums[mid]){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
    }
    
    
    return -1
};