[LC] 0033 Search in Rotated Sorted Array

Java

/**
 * <a href="https://leetcode.cn/problems/search-in-rotated-sorted-array/">Search in Rotated Sorted Array</a>
 * 数组；二分查找
 */
class Solution {
    public int search(int[] nums, int target) {
        if (nums.length == 0) {
            return -1;
        }
        if (nums.length == 1) {
            return nums[0] == target ? 0 : -1;
        }

        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                return mid;
            }

            if (nums[l] <= nums[mid]) { // 左半部分有序
                if (nums[l] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {    // 右半部分有序
                if (nums[mid] < target && target <= nums[r]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }

        return -1;
    }
}

Go

func search(nums []int, target int) int {
    n := len(nums)
    if n == 0 {
        return -1
    }
    if n == 1 {
        if nums[0] == target {
            return 0
        }
        return -1
    }

    l, r := 0, n-1
    for l <= r {
        mid := l + (r-l)/2
        if nums[mid] == target {
            return mid
        }

        if nums[l] <= nums[mid] { // left sorted
            if nums[l] <= target && target < nums[mid] {
                r = mid - 1
            } else {
                l = mid + 1
            }
        } else { // right sorted
            if nums[mid] < target && target <= nums[r] {
                l = mid + 1
            } else {
                r = mid - 1
            }
        }
    }

    return -1
}

JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
    if (nums.length === 0) {
        return -1;
    }
    if (nums.length === 1) {
        return nums[0] === target ? 0 : -1;
    }

    let l = 0;
    let r = nums.length - 1;
    while (l <= r) {
        let mid = Math.floor((l + r) / 2);
        if (nums[mid] === target) {
            return mid;
        }

        if (nums[l] <= nums[mid]) {
            if (nums[l] <= target && target < nums[mid]) { // left sorted
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        } else {    // right sorted
            if (nums[mid] < target && target <= nums[r]) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
    }

    return -1;
};

PHP

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function search(array $nums, int $target): int {
        $n = count($nums);
        if ($n == 0) {
            return -1;
        }
        if ($n == 1) {
            return $nums[0] == $target ? 0 : -1;
        }

        $l = 0;
        $r = $n - 1;
        while ($l <= $r) {
            $mid = $l + floor(($r - $l) / 2);
            if ($nums[$mid] == $target) {
                return $mid;
            }

            if ($nums[$l] <= $nums[$mid]) { // left sorted
                if ($nums[$l] <= $target && $target < $nums[$mid]) {
                    $r = $mid - 1;
                } else {
                    $l = $mid + 1;
                }
            } else {    // right sorted
                if ($nums[$mid] < $target && $target <= $nums[$r]) {
                    $l = $mid + 1;
                } else {
                    $r = $mid - 1;
                }
            }
        }

        return -1;
    }
}