LeetCode 33. Search in Rotated S

题目

33. Search in Rotated Sorted Array

题解

题目意思就是在一个上升序列中截断成AB 两个子序列 然后BA拼接成一个新的序列， 而题目要求 我们查找在这个序列中是否存在target，如果看到这里就会发现 这个很简单啊，查找一个序列中是否有某个数字 直接遍历就好了 方法木佬佬，但是 最重要的是题目末尾有一句

Your algorithm's runtime complexity must be in the order of O(log n).

你的程序运行时间必须是 O(log n)， 看到Ologn 我脑海里第一反应就是二分。
因为是一个上升序列截成两段实际就是两个上升序列 所以在二分的时候会出现一部分 nums[l] >nums[r] 不过这时候 只要判断 target 是否存在于另一段有序序列中就行了， 毕竟两者去除一个不存在的 就好了
最后判断是否存在 不存在 返回 -1
最坑的一点这个输入会出现空序列 要进行特判 特判 特判

代码

fun search(nums: IntArray, target: Int): Int {
    var l = 0
    var r = nums.size - 1
    if (nums.isEmpty())
        return -1
    return binary(nums, l, r, target)
}

fun binary(nums: IntArray, l: Int, r: Int, target: Int): Int {
    var mid = (l + r) / 2

    if (nums[mid] == target)
        return mid
    if (l >= r)
        return -1
    return if (nums[mid] < nums[r]) {
        if (nums[mid] < target && nums[r] >= target) {
            binary(nums, mid + 1, r, target)
        } else {
            binary(nums, l, mid - 1, target)
        }
    } else {
        if (nums[l] <= target && nums[mid] > target) {
            binary(nums, l, mid - 1, target)
        } else {
            binary(nums, mid + 1, r, target)
        }
    }
    return -1
}

结果

image.png