153. Find Minimum in Rotated Sorted Array
Solution
這題會給你一個排序好的陣列 nums，但是這個陣列可能會位移幾格。假設陣列裡面有 [1, 2, 3, 4, 5, 6, 7]，可能會位移成 [3, 4, 5, 6, 7, 1, 2]。這題的目的是找出這個陣列裡面最小的數字，在這個情況是 index = 5 的位置，也就是 1。
這題可以用二分搜去找到最小的數字，不過判斷的方式會不太一樣，我們可以觀察搜尋時分析往左邊找的情況，和往右邊找的情況。
如果
nums[m]比nums[l]和nums[r]大，那我們就會往右半邊搜尋。以下面的情況來看，6比3和2大，可以觀察到最小的數字在右半邊。3 4 5 6 7 1 2 l m r如果
nums[m]比nums[l]和nums[r]小，那我們就會往右半邊搜尋。以下面的情況來看，2比6和5大，可以觀察到最小的數字在左半邊。6 7 1 2 3 4 5 l m r
那如果陣列沒有動過怎麼辦？如果是正常排序好的話，nums[m] 會被夾在 nums[l] 和 nums[r] 中間，不會符合上面兩種情況。在這個情況下最小的數字一定在最左邊，因此二分搜時會一直往左半邊搜尋，因此以下的程式碼就直接讓他走 else 這個區塊，因此下面的 if 和 else 不會反過因此
到最後結束搜尋時，通常 nums[l] 會是最大的數字，nums[r] 則會是最小的數字，也就是 nums[l] 的下一個。但nums 如果沒有位移過，那 nums[l] 會是最小的數字， nums[r] 會是第二小的數字。因此最後還需要判斷這兩個數字誰比較小，並且回傳最小的數字。
Implementation
class Solution {
fun findMin(nums: IntArray): Int {
var l = 0
var r = nums.lastIndex
while (r - l > 1) {
val m = (l + r) / 2
if (nums[m] > nums[l] && nums[m] > nums[r]) l = m
else r = m
}
return if (nums[l] > nums[r]) return nums[r] else nums[l]
}
}