leetcode_practice/33. Search in Rotated Sorted Array.kt at main · Cyberavater/leetcode_practice · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    fun search(nums: IntArray, target: Int): Int {

        fun reSearch(l: Int, r: Int): Int {
            val midIndex = (l + r) / 2

            if (l <= r) {
                if (nums[midIndex] == target) {
                    return midIndex
                } else {

                    val partitionAtLeft = nums[l] > nums[midIndex]

                    return if (partitionAtLeft) {
                        if (target >= nums[l] || target < nums[midIndex]) {
                            reSearch(l, midIndex - 1)
                        } else {
                            reSearch(midIndex + 1, r)
                        }

                    } else {
                        if (target < nums[l] || target > nums[midIndex]) {
                            reSearch(midIndex + 1, r)
                        } else {
                            reSearch(l, midIndex - 1)
                        }
                    }

                }
            } else {
                return -1
            }
        }

        return reSearch(0, nums.lastIndex)
    }
}