Leetcode 33. 搜索旋转排序数组

33. 搜索旋转排序数组

解法：排序数组，第一时间想到的应该是二分

但这题二分细节较多，思路需要捋清楚，除了对比二分的位置，还需要考虑需要旋转后的阶段性有序。

代码：这里有两个讨论点，可以看到对比时，使用的是nums[0]和 nums[nums.size -1]，我在提交时先后将 nums[num.size-1]换成了nums[r],nums[0]换成了 nums[l]，在 leetcode 中测试用例中均可通过。

时间复杂度： O(log n) 空间复杂度：O(1)

这时候我的脑子告诉我：“算了吧，这我也捋不清”，然后我去看下了其他评论，都差不多是把官方的思路换了个写法，明显可以感觉到的是，使用[0]和[size – 1]会将范围放大，在更大的更复杂的样本会更可靠？日后水平提高再确认。

class Solution {
    fun search(nums: IntArray, target: Int): Int {
        if (nums.isEmpty()) return -1
        if (nums.size == 1) {
            if (nums.first() == target) return 0 else -1
        }
        var l = 0
        var r = nums.size - 1
        while (l <= r) {
            val mid = l + (r - l) / 2
            if (nums[mid] == target) return mid
            if (nums[0] <= nums[mid]) {
                //左侧为有序
                if (nums[0] <= target && target < nums[mid]) {
                    //target 在[left,mid]这个有序范围内
                    r = mid - 1
                } else {
                    l = mid + 1
                }
            } else {
                if (nums[mid] < target && target <= nums[nums.size - 1]) {
                    //如果右侧有序并在这个范围内
                    l = mid + 1
                } else {
                    r = mid - 1
                }
            }
        }
        return -1
    }
}