python3 解法, 执行用时: 36 ms, 内存消耗: 15.8 MB, 提交时间: 2022-12-02 11:28:20

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        left, right = 0, len(nums) - 1
        while left < right:                                         # 循环结束条件left==right
            mid = (left + right) >> 1
            if nums[left] < nums[mid]:                              # 如果左值小于中值，说明左边区间升序 
                if nums[left] <= target and target <= nums[mid]:    # 如果目标在左边的升序区间中，右边界移动到mid
                    right = mid
                else:                                               # 否则目标在右半边，左边界移动到mid+1
                    left = mid + 1
            elif nums[left] > nums[mid]:                            # 如果左值大于中值，说明左边不是升序，右半边升序
                if nums[left] <= target or target <= nums[mid]:     # 如果目标在左边，右边界移动到mid
                    right = mid
                else:                                               # 否则目标在右半边的升序区间中，左边界移动到mid+1
                    left = mid + 1
            elif nums[left] == nums[mid]:                           # 如果左值等于中值，可能是已经找到了目标，也可能是遇到了重复值
                if nums[left] != target:                            # 如果左值不等于目标，说明还没找到，需要逐一清理重复值
                    left += 1                                        
                else:                                               # 如果左值等于目标，说明已经找到最左边的目标值
                    right = left                                    # 将右边界移动到left，循环结束
        return left if nums[left] == target else -1                 # 返回left，或者-1

java 解法, 执行用时: 0 ms, 内存消耗: 42.1 MB, 提交时间: 2022-12-02 11:27:53

class Solution {
    public int search(int[] arr, int target) {
        if (arr[0] == target) {
            return 0;
        }
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) >>> 1;
            if (arr[mid] == target) {
                while (mid > 1 && arr[mid - 1] == arr[mid]) {
                    mid--;
                }
                return mid;
            } else if (arr[mid] > arr[left]) {
                if (arr[left] <= target && target < arr[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else if (arr[mid] < arr[left]) {
                if (arr[mid] < target && target <= arr[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else {
                left++;
            }
        }
        return -1;
    }
}

javascript 解法, 执行用时: 72 ms, 内存消耗: 41.5 MB, 提交时间: 2022-12-02 11:26:54

/**
 * @param {number[]} arr
 * @param {number} target
 * @return {number}
 */
var search = function (arr, target) {
    let len = arr.length
    let left = 0
    let right = len - 1
    //去重
    while (right > 0 && arr[0] == arr[right]) right--;
    //用二分找到原数组最后的元素（首尾相连点）
    //这样左侧和右侧各是一个升序数组
    while (left < right) {
        let mid = Math.floor((right - left + 1) / 2) + left
        if (arr[mid] >= arr[0]) {
            left = mid
        } else {
            right = mid - 1
        }
    }
    //判断target在翻折点的左侧还是右侧
    if (arr[0] > target) {
        left += 1
        right = len - 1
    } else {
        left = 0
    }
    while (left < right) {
        let mid = Math.floor((right - left) / 2) + left
        if (arr[mid] >= target) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return arr[right] == target ? right : -1
};