算法之二分法

说一说二分法，上次看到了，一直没做总结，跻身于待办事项里有些日子了，今天看它不顺眼，给它解决掉

二分法，用来查找目标值，前提是有序数组。顾名思义，就是定义两个指针，一个指向最低位置，另个指向最高位置，每次取中以求减少循环次数，时间复杂度是O(logn)。二分法查找时，会有3种情况，一个是找到目标值即返回，一个是找到最左值，还有一个自然是找到最右值。后两者存在于数组中存在多个目标值的情况。

接下来的几段代码中，都用下面这个数组，长度是14

1	val arr = intArrayOf(2, 3, 4, 4, 8, 12, 21, 21, 21, 23, 45, 54, 54, 98)

1. 查找目标值

这个时候，不关心有几个，只关心有，还是没有，找到就返回，找不到就算了

fun findValue(target: Int): Int {
    var low = 0
    var high = arr.size - 1
    // point 0
    while (low <= high) {
    	// point 1
        val med = low + (high - low) / 2
        if (arr[med] == target) {
            return med
        }
        if (arr[med] > target) {
        	// point 2
            high = med - 1
        } else {
        	// point 3
            low = med + 1
        }
    }
    return -1
}

fun main() {
    val target = 54
    val index = findValue(target)
    println("find value of $target, size:${arr.size}, index:$index")
}

// 输出：find value of 54, size:14, index:12

需要有几点注意的地方，

一个是while的停止条件，因为在这low和high都是数组的角标，所以它们是可能相等，所以是小于等于。我觉得不要考虑太多的情况，记的多了反而容易乱
再一个就是计算med时，为防止溢出，不要把两个相加再除以2
最后一个就是更新low和high的值时，要跳过med，因为med已经比较过了，不要再重复

2. 找最左值

当数组中存在多个目标值的时候，找到处于最左边的那个，

fun findLeftValue(target: Int): Int {
    var low = 0
    var high = arr.size - 1
    while (low <= high) {
        val med = low + (high - low) / 2
        // point 0
        if (arr[med] < target) {
            low = med + 1
        } else {
            high = med - 1
        }
    }
    if (low < arr.size && arr[low] == target) {
        return low
    }
    return -1
}

fun main() {
    val target = 1
    val index = findLeftValue(target)
    println("find value of $target, size:${arr.size}, index:$index")
}

// 输出：find value of 54, size:14, index:11

与上面的不同，这个不是找到就返回，而是将high不停的向左靠，直到和low相遇，这个时候才会结束while循环

只有在target比med大的时候，移动low，剩下的情况，移动high，逼近low。
情况一，med命中target，且数组中只有一个target，但这时会移动high，到med-1，在接下来的循环中，low就会不停的向high靠拢，直到和high相遇，因为target在high的右边，这个时候med的值小于target，移动low到med+1，超过了high，退出循环，此时low就是target的位置
情况二，target不在数组中，比最左还要小，此时，循环结束后，high会移动到low的左边-1的位置
情况三，target不在数组中，比最右还要大，此时，循环结束后，low会移动到high的右边arr.size的位置，超出数组范围
结合这几种情况，在while结束后，再加一个判断，就可以得到最后的结果了

3. 找最右值

这个和找最左值刚好相反，如果上面的能明白，这个就也可以明白

fun findRightValue(target: Int): Int {
    var low = 0
    var high = arr.size - 1
    while (low <= high) {
        val med = low + (high - low) / 2
        if (arr[med] > target) {
            high = med - 1
        } else {
            low = med + 1
        }
    }
    if (high >= 0 && arr[high] == target) {
        return high
    }
    return -1
}

fun main() {
    val target = 21
    val index = findRightValue(target)
    println("find value of $target, size:${arr.size}, index:$index")
}

// 输出：find value of 21, size:14, index:8

题外话

想着用kotlin写，顺便练习一下，就打开了IntelliJ IDEA，发现破解无效了，可能是太久没用了吧。其实也不是破解，就是无限重置30天试用的那个时间，以达到长期白嫖的目的。现在这个版本要登陆账号了，门槛又高了，心想着登陆了账号后，不出意外肯定会把试用时间和账号关联，这不就成一次性的了吗？于是，就开始往下降版本，一路卸载、下载安装包、再安装，直到2021.1，才可以，这熟悉的味道又回来了。

2021.1，记住这个版本，这是一个不可跨越的分水岭。