昨天的左右雙指標還有一點點內容

反轉陣列

給定一個陣列，如何反轉這個陣列呢？

一般來說，程式語言都會提供這個api，不過我們還是來看看用左右雙指標怎麼實現這個功能

fun reverseArray(nums: Array<Int>): Array<Int> {
    var left = 0
    var right = nums.size - 1
    while (left < right){
        //交換兩者的數值
        val temp = nums[left]
        nums[left] = nums[right]
        nums[right] = temp
        left++
        right--
    }
    return nums
}

這個很簡單就不展示執行結果了

二分搜尋演算法

昨天我們有提到二分搜尋演算法，今天就來聊一下

先來看看二分演算法的框架

fun binarySearch(nums: Array<Int>, target: Int) :Int{
    var left = 0;
    var right = ...
    while(...){
        val mid = left + (right-left) /2
        if(nums[mid] == target){
            ...
        }else if(nums[mid] < target){
            ...
        }else if(nums[mid] > target){
            ...
        }
    }
    return ...
}

在上面的sudo code 中 ，”…”的地方都是很有可能出現細節問題的地方，一但見到二分搜尋演算法，這邊的Code需要特別的注意．

另外有一個可以小技巧，在計算mid的時候，要小心數值溢出，造成溢位．

(left+right)/2跟left + (right-left) /2的結果是相同的，但是left+right在某些特別大的情況就會發生問題，改變寫法可以減少這樣的問題的發生．

最後有個重點是，不要使用else，而是使用else if把所有可能都列出來，有時候走進了else很有可能超出了預想的情境．

找尋一個數

這是最基本二分搜尋問題，在一個陣列中尋找，如果有找到就返回index，沒有找到就返回-1

讓我們帶入上面的框架來試試看吧

fun binarySearchOriginal(nums: Array<Int>, target: Int): Int {
    var left = 0
    var right = nums.size - 1//注意點
    while (left <= right) {//注意點
        val mid = left + (right - left) / 2
        when {
            nums[mid] == target -> {
                return mid
            }
            nums[mid] < target -> {
                left = mid + 1//注意點
            }
            nums[mid] > target -> {
                right = mid - 1//注意點
            }
        }
    }
    return -1
}

1.為什麼while的條件是<= 而不是 < ?

因為初始化right的數值是nums.size-1，代表的是Array的最後一個的索引．

nums.size-1 與nums.size會出現在不同功能的二分搜尋中

一個代表的是 [left,right] 兩邊都是閉區，而另外一個使用在 [left,right)的情況，代表左閉又開區間

這次演算法是使用 [left,right] 的區間，代表每次搜尋的區間．

在什麼時候停止搜尋呢？一個當然是找到答案了，就能直接回傳．另外一個就是這個區間空了沒得找了．

while的條件 正是描述這一情況，當區間縮到變成[right+1,right]時，自然不存在任何的可能性

如果把搜尋條件寫成 while(left < right) ，那當left與right相等的那次迴圈就不會檢查，有可能會遺漏答案

2.為什麼下一次while迴圈的left跟right分別是left = mid + 1跟right = mid - 1 ，而有些就是left = mid或是right = mid，怎麼分辨？

這是二分演算法困難的一個地方，如何去決定下個迴圈．

在這個題目裡面，我們已經確定mid不是target，所以根據現在mid與target個關係，去mid-1或是mid+1的區塊去尋找，可以省下一次檢查計算．

3.這個演算法有什麼缺點?

在某些特定的題目下，無法優雅得到答案．例如題目的nums = [1,2,3,3,3,4,5], target = 3．這個演算法就會返回正中央的索引，也就是3，但是如果題目要找左側邊界或是右側邊界，這個演算法就無能為力了．

雖然可以利用中間的target索引，左右去線性一步一步走到不是target的索引，這樣可以達成目的，但是難以確保二分搜尋對數級的複雜度

明天我們會來看看這個問題的二分搜尋法