Day2

1 搜索旋转排序数组

分析

1. 要求时间复杂度为 \(\Theta(\log(n))\)，目前已知二分查找的复杂度符合
2. 旋转排序数组的特征是从某个位置切下后两边都为有序数组，而从其他位置切下时将会得到一个有序一个无序。

伪代码

\begin{algorithm} \caption{searchRotated(A, target)} \begin{algorithmic} \State first = 0, last = A.length - 1 \While{first <= last} \State mid = $\lfloor first + (last - first)/2 \rfloor$ \Comment{计算中间索引} \If{A[mid] == target} \State \Return mid \Comment{如果中间值等于目标值，返回索引} \EndIf \If{A[first] <= A[mid]} \If{A[first] <= target \And target < A[mid]} \State last = mid - 1 \Comment{目标值在左侧有序子数组中} \Else \State first = mid + 1 \Comment{目标值在右侧子数组中} \EndIf \Else \If{A[mid] < target \And target <= A[last]} \State first = mid + 1 \Comment{目标值在右侧有序子数组中} \Else \State last = mid - 1 \Comment{目标值在左侧子数组中} \EndIf \EndIf \EndWhile \State \Return -1 \Comment{未找到目标值，返回-1} \end{algorithmic} \end{algorithm}

Python

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        """
        采用二分法，通过二分法，原数组一定可以变成一部分有序，另一部分无序，通过判断是否在有序部分，若在则可继续二分法，反之则在无序部分继续二分，进行判断。
        """
        low = 0; upper = len(nums) - 1
        while low <= upper:
            mid = (low + upper) // 2
            if target == nums[mid]:
                return mid
            if nums[low] <= nums[mid]:  # 左侧为有序部分
                if nums[low] <= target and target <= nums[mid]:
                    upper = mid - 1  # 在左侧
                else:
                    low = mid + 1  # 保证不会出现6, 7一直处在6的情况
            else:  # 右侧为有序部分
                if nums[mid] <= target and target <= nums[upper]:
                    low = mid + 1
                else:
                    upper = mid - 1
        return -1

C++

int searchRotated(vector<int>& nums, int target){
    int first = 0, last = nums.size() - 1;
    while (first<=last){
        int mid = first + (last - first) / 2;
        if (nums[mid]==target){
            return mid;
        }        
        if (nums[first]<=nums[mid]){
            if (nums[first]<=target && nums[mid]>target){
                last = mid - 1;
            }
            else first = mid + 1;
        }
        else{
            if (nums[mid]<target && nums[last]>=target){
                first = mid + 1;
            }
            else last = mid - 1;
        }
    }
    return -1;
}

2 搜索旋转排序数组Ⅱ

分析

该问题与上一个问题的区别在于元素可重复，元素可重复并没有改变当从数组中间切一刀时将会得到一个有序的子数组和一个无序的子数组的事实，但是会造成无法通过A[first]<=A[mid]来判断是否为有序数列如[1,3,1,1,1]，因此需要修改。 - 若A[first]<A[mid]，则必可说明A[first..mid]为有序数组。 - 若A[first]>A[mid]，则必可说明A[first..mid]为无序数组，A[mid..last]为有序数组。 - 若A[first]=A[mid]，则可通过first=first+1的形式避免这种情况，由于mid处和first处值一致因此直接删除first处的值也无碍。

伪代码

\begin{algorithm} \caption{searchRotated2(nums, target)} \begin{algorithmic} \State $first \gets 0$ \State $last \gets \text{length}(nums) - 1$ \While{$first \leq last$} \State $mid \gets \lfloor first + \frac{(last - first)}{2} \rfloor$ \If{$nums[mid] = target$} \State \Return true \EndIf \If{$nums[first] < nums[mid]$} \If{$nums[first] \leq target \And target < nums[mid]$} \State $last \gets mid - 1$ \Else \State $first \gets mid + 1$ \EndIf \ElsIf{$nums[first] > nums[mid]$} \If{$nums[mid] < target \And nums[last] \geq target$} \State $first \gets mid + 1$ \Else \State $last \gets mid - 1$ \EndIf \Else \State $first \gets first + 1$ \EndIf \EndWhile \State \Return $false$ \end{algorithmic} \end{algorithm}

Python

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        """
        这题用上一题的判断有序的方法会造成无法判断[1, 3, 1, 1, 1] -> 原来的方法会导致两边都是有序的，因此得用其它方式进行判断
        1. 若大于或小于便一定可以以判断有序的部分
        2. 相等的时候，则可以继续搜索用low += 1进行搜索
        """
        low = 0; upper = len(nums) - 1
        while low <= upper:
            mid = (low + upper) // 2
            if nums[mid] == target:
                return True
            if nums[low] == nums[mid]:
                low += 1
            elif nums[low] < nums[mid]:
                if target >= nums[low] and target <= nums[mid]:
                    upper = mid - 1
                else:
                    low = mid + 1
            else:
                if target >=nums[mid] and target <= nums[upper]:
                    low = mid + 1
                else:
                    upper = mid - 1
        return False 

C++

bool search(vector<int>& nums, int target) {
        int first = 0, last = nums.size() - 1;
        while (first<=last){
            int mid = first + (last - first) / 2;
            if (nums[mid]==target){
                return true;
            }        
            if (nums[first]<nums[mid]){
                if (nums[first]<=target && nums[mid]>target){
                    last = mid - 1;
                }
                else first = mid + 1;
            }
            else if (nums[first]>nums[mid]){
                if (nums[mid]<target && nums[last]>=target){
                    first = mid + 1;
                }
                else last = mid - 1;
            }
            else first++;
        }
        return false;
    }