2022-09-26

[gongpeione]

33 Search in Rotated Sorted Array

/*
 * @lc app=leetcode id=33 lang=typescript
 *
 * [33] Search in Rotated Sorted Array
 * [7(l),8,9,0,1,2(m),3,4,5,6(r)]
 */

// @lc code=start
function search(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        const middle = ~~((right + left) / 2);

        if (nums[middle] === target) {
            return middle;
        }

        // left portion
        if (nums[left] <= nums[middle]) {
            if (nums[left] > target || nums[middle] < target) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        // right portion
        else {
            if (target < nums[middle] || target > nums[right]) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
    }

    return -1;
};
// @lc code=end

---

Nickname: Geeku From vscode-hzfe-algorithms