Leetcode題解 Python & C#：四月挑戰DAY19 Search in Rotated Sorted Array

今天有C#，因為我看蠻多ASP的工作缺，練習ASP也得加強C#。

給一串數組，經過排序但旋轉過(向右移動?次)，且每個數字不重複，並且要求在時間複雜度 O(log n) 解決。

最直覺地使用 for 迴圈，但時間複雜度會是 O(n) ，不符合要求。

說到 O(log n) ，二分搜尋是最典型的方法。用兩次二分搜尋，一次是找到排序的分界(最大值)，二是從分界往左或右找到目標值。O(log 2n) => O(log n)

設左界 l 右界 r，中間為 m = (r-l)/2 + l 。第一次找將比對目標 t 先設為 nums[0] ，如果 nums[m] > t ，更新 t 並移動左界 l = m+1，否則不更新 t 但移動右界 r = m。

直到 l == r，此時為 nums[l] or nums[r] 都是最大值。

若目標值 target 小於 nums[0] ，表示目標值在最大值右方，否則在最大值左方。針對情況移動右界至nums的長度或左界至0。

再用一次二分搜尋法，這次的比對目標就是 target，當 l 等於 r 時沒有找到就回傳 -1 ，其餘為當下的索引 m 。


PYTHON3

class Solution:       
    def search(self, nums: List[int], target: int) -> int:
        if not nums: return -1
        maxNum = nums[0]
        n = len(nums)
        l, r = 0, n
        while l < r:
            m = (r-l)//2 + l
            if nums[m] >= maxNum:
                maxNum = nums[m]
                l = m+1
            else:
                r = m
        #
        if target < nums[0]: r = n    
        else: l = 0     
        #
        while l < r:
            m = (r-l)//2 + l
            if nums[m] == target:
                return m
            elif nums[m] > target:
                r = m
            else:
                l = m + 1
        return -1

C#

public class Solution {
    public int Search(int[] nums, int target) {        
        int r = nums.Length;
        if(r==0){return -1;}
        int l = 0;
        int maxNum = nums[0];
        // 先找出最大值的位置
        while(l < r){
            int m = (r-l)/2+l;
            if(nums[m] >= maxNum){
                maxNum = nums[m];
                l = m+1;
            }else{
                r = m;
            }
        }
        //從中間開始找
        if(target < nums[0]){
            r = nums.Length;
        }else{
            l = 0;
        }
        //
        while(l < r){
            int m = (r-l)/2+l;
            if(nums[m] == target){
                return m;
            }else if(nums[m] < target){
                l = m+1;            
            }else{
                r = m;
            }
        }       
        return -1;
    }
}