昨天我們看了最基礎的二分演算法，但是也發現了她有些問題，比如說要找到左右邊界的問題就沒辦法做到，我們今天來改寫這個演算法．讓他可以找到左右邊界

讓我們來小小修改一下

搜尋左邊界

fun binarySearchLeftEdge(nums: Array<Int>, target: Int): Int {
    if (nums.isEmpty()) {
        return -1
    }
    var left = 0
    var right = nums.size //注意點
    while (left < right) {//注意點
        val mid = left + (right - left) / 2
        when {
            nums[mid] == target -> {
                right =  mid //修改右邊界
            }
            nums[mid] < target -> {
                left = mid + 1
            }
            nums[mid] > target -> {
                right = mid//注意點
            }
        }

    }
    return left//注意

}

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

因為這次的搜尋區間需要左閉右開，是變成[left, right)，這樣寫的話，迴圈的停止條件會出現在

left == right的時候，此時搜尋區間[left,left)為空，因此可以正確終止

其實要寫的兩端都閉其實也可以，甚至可以寫得更簡單，但是在搜尋左右邊界的演算法，這種寫法比較普遍．

2.為什麼不返回-1了，如果找不到target怎麼辦？

我們來稍微思考一下．

用以下這個例子

val nums = arrayOf(1, 2, 2, 2, 3)
val target = 2

對於這個測資，演算法會返回1，代表2的左邊界在index 1的位置

站在另外一個角度，既然Array已經經過排序了，target = 2的左邊界在index =1的位置，也就代表array中有1個元素是小於2的

由此可知，現在的函數返回值(就是最後的return left)的取值區間是閉區[0,nums.size]，所以當回傳時補上兩行，就可以在正確時返回-1

while(...){
}

if(left == nums.size){
 return -1 //target比Array中的所有數字都大，顯然不存在Array中
}else{
return nums[left] == target ? left :-1
}

3.為什麼各種條件的處理變成 left = mid+1 或是right = mid？跟之前差好多喔

同樣是搜尋區間的原因，這次是[left,right)的左閉右開，所以在檢查nums[mid]後，該做的是去掉mid所代表的數值，然後分隔成兩個搜尋區間，亦即 [left, mid) 或是[mid+1,right)

(左右條件不同 ，去掉mid的方式也不同)

4.為什麼會這樣就能搜尋左邊界呢?

魔法在這裡

 nums[mid] == target -> {
                right =  mid //修改右邊界
            }

之前找到答案就直接回傳，而這次找到答案後縮小搜尋區間的邊界，然後在[left,mid)中繼續搜尋，亦即不停向左收縮，最後會夾緊左邊界．

5.我不管拉我就是要寫兩端都閉的版本，和昨天的不統一我不舒服

因為要求要兩端都閉，因此

⇒初始化right的時候使用 right = nums.size-1

⇒while變為在 left = right+1 時終止

⇒所以while迴圈的判斷條件改為使用 < =

根據以上思路，修改如下

fun binarySearchLeftEdgeClosEdge(nums: Array<Int>, target: Int): Int {
    if (nums.isEmpty()) {
        return -1
    }
    var left = 0
    var right = nums.size - 1//搜尋區間[left, right]
    while (left <= right) {
        val mid = left + (right - left) / 2
        when {
            nums[mid] < target -> {
								//搜尋區間變為[mid+1, right]
                left = mid + 1
            }
            nums[mid] > target -> {
								//搜尋區間變為[left, mid-1]
                right = mid -1
            }
            nums[mid] == target -> {
								//收縮右側邊界
                right = mid -1
            }
        }
    }
    
    if( left >= nums.size||nums[left] != target){//檢查越界情況
        return -1
    }
    return left
}

因為兩端都閉，left和right更新邏輯要修改搜尋區間．

由於while的退出條件改成 left == right +1 ，因此target比nums 所有元素大時，會indexOutOfBound，因此，最後返回的時候要檢查越界情況．

搜尋右邊界

其實內容跟搜尋左邊界差不多，差別只在初始

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

    }
    return left -1 //不同點

}

1.為什麼會這樣就能搜尋右邊界呢?

同樣的魔法再用一次

 nums[mid] == target -> {
                right =  mid //修改右邊界
            }

同樣的，一改找到答案就直接回傳，而這次找到答案後”增大”搜尋區間的邊界，即不停向右擴張，最後會鎖定右邊界．

2.為什麼返回 left -1 ，而不是向左側邊界那樣回傳left?而且既然要搜尋右邊界應該回傳right?

因為while迴圈的終止條件是left == right，最後left跟right一樣，所以其實也能回傳right -1就可以．

至於為什麼要減1，這是右側邊界的特點，關鍵在於

nums[mid] == target -> {
    left = mid +1 
    //所以 mid = left -1
}

因為針對left的更新是left = mid +1 ，因此while終止時，nums[left]一定不是target，而nums[left-1]就可能等於target

3.為什麼沒有返回-1的操作…..以下略

略 所以我們加上兩行

while(...){
}

if(left == 0){
    return -1
}
else {
    return nums[left-1] == target? (left-1):-1
}

4.我不管拉我就是要寫兩端都閉的版本…(略

這樣就能夠完全統一寫法了，同樣的也只要改兩個地方．

fun binarySearchRightEdgeClosEdge(nums: Array<Int>, target: Int): Int {
    if (nums.isEmpty()) {
        return -1
    }
    var left = 0
    var right = nums.size - 1//搜尋區間[left, right]
    while (left <= right) {
        val mid = left + (right - left) / 2
        when {
            nums[mid] < target -> {
                left = mid + 1
            }
            nums[mid] > target -> {
                right = mid -1
            }
            nums[mid] == target -> {
                //這邊改成收縮左側邊界
                left = mid +1
            }
        }
    }

    if( right <0||nums[right] != target){//這邊改成檢查right越界情形
        return -1
    }
    return right
}