# 33. Search in Rotated Sorted Array

題目：<https://leetcode.com/problems/search-in-rotated-sorted-array/>

解法：二分搜尋法，切半時其中一半會維持 rotated sorted array，另外一半則會是一般的 sorted array，辨別出來後再判斷 target 在哪一邊並更新即可。

Python3：

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] >= nums[left]:
                if nums[mid] > target and nums[left] <= target:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target and nums[right] >= target:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1

if __name__ == '__main__':
    # nums = [4, 5, 6, 7, 0, 1, 2]
    # target = 0
    nums = [3,1]
    target = 1

    ans = Solution().search(nums, target)
    print(ans)

C：

#include <stdio.h>
#include <stdlib.h>

int search(int* nums, int numsSize, int target) {
    int left = 0, right = numsSize - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target)
            return mid;
        if (nums[mid] >= nums[left]) {
            if (nums[mid] > target && nums[left] <= target)
                right = mid - 1;
            else
                left = mid + 1;
        } else {
            if (nums[mid] < target && nums[right] >= target)
                left = mid + 1;
            else
                right = mid - 1;
        }
    }
    return -1;
}

int main()
{
    int nums[] = {3, 1};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int target = 1;
    
    int ans = search(nums, numsSize, target);
    printf("%d\n", ans);
    return 0;
}

###### tags: `leetcode` `binary search`