昨天講了快慢指標，我們今天來看看左右雙指標可以做什麼

二分搜尋

這個二分搜尋的整體框架我們在未來會講到，今天先展示一下左右雙指標的特性

左右雙指標通常一個初始化在陣列的起頭，而另外一個初始化在陣列的末端．

fun binarySearch(nums: Array<Int>, target: Int): Int {
    //左右雙指標在兩端初始化
    var left = 0
    var right = nums.size - 1
    while (left <= right) {
        val mid: Int = (right + left) / 2 //對半尋找
        when {
            nums[mid] == target -> {// 找到目標值
                return mid
            }
            nums[mid] < target -> { //目標在兩份數字中 比較大的那邊
                left = mid + 1
            }
            nums[mid] > target -> { //目標在兩份數字中 比較小的那邊
                right = mid - 1
            }
        }
    }
    return -1//沒有找到
}

我們用這個概念來解個題目吧

兩數之和

直接來看看題目: ˋ給一個排列好的升冪陣列nums，以及一個要尋找的目標值target，在nums陣列中找到兩個數字，他們的總和等於target，然後返回這兩個數字的索引值．(假設目標值一定存在，索引從1開始)

例如輸入 nums = [2,7,11,15] target為13，則應該返回 [1,3]

只要是有序的陣列，就應該想到雙指標技巧

思考一下，既然有序，也就是說target跟目前雙指標所指的數值總和關係可以調整．

當雙指標總和大於目標值，那就讓雙指標的總和小一點

⇒尾巴位置的指標往較小的方向移動，讓兩個指標的總和減少

當雙指標總和小於目標值，那就讓雙指標的總和大一點

⇒起始位置的指標往較大的方向移動，讓兩個指標的總和增加

最後總有一天會剛好為目標數值

讓我們來寫寫看

fun twoSum(nums: Array<Int>, target: Int): Pair<Int, Int> {
    var left = 0
    var right = nums.size - 1
    while (left < right) {
        val tempSum = nums[left] + nums[right]
        println("tempSum is $tempSum, from left value "+nums[left]+ " and right value "+nums[right])

        when {
            tempSum == target -> {
                return Pair(left + 1, right + 1) // 題目要求從1開始
            }
            tempSum < target -> {//讓總和大一點
                left++
            }
            tempSum > target -> {//讓總和小一點
                right--
            }
        }
    }
    return Pair(-1,-1)//沒有找到
}

使用以下測資來測試看看吧

fun main() {
    val nums = arrayOf(2, 7, 11, 15,16,18,21)
    val target = 33
    println(twoSum(nums,target))
}

結果如下

明天會繼續看看左右指標