Android 算法知识系列：二进制搜索

理论知识

二分查找又称对半查找。

过程:用目标值对比中间值，通过移动中间标志位，循环直到找到目标值或者跳出循环。

前提:数据是排好序的。

常用标志

以下为二分法代码中常用的字段

标志	备注
left	左侧标识位
right	右侧标志位
mid	中间标志位
target	目标值

基本二分法

案例：一个数组[1,2,3,5,7,8,10]，查找目标值 3 的位置。
答案：2

代码

/**
* 基本二分查找
* numArray 数组
* target 目标值
*
* @return 目标值的位置，没有匹配到则为-1
*/
fun binaryForTarget(numArray: IntArray, target: Int): Int {
    if (numArray.isEmpty()) {
       return -1
    }
    var left = 0
    var right = numArray.size - 1
    while (left <= right) {
        val mid = left + (right - left) / 2 //防止溢出
        when {
            numArray[mid] == target -> {
                return mid
            }
            numArray[mid] > target -> {
                right = mid - 1
            }
            numArray[mid] < target -> {
                left = mid + 1
            }
        }
    }
    return -1
}

//目标值的位置是2
WxSolution.binaryForTarget(intArrayOf(1,2,3,5,7,8,10),3)

推导流程

流程图解

细节强调

1. mid 中间值的求法
   left+(right-left)/2 这种计算方式可以有效防止溢出错误。
2. 判断条件 left <= right
   等于是为了能够遍历到最后一个数据，防止漏数据。
3. left=mid+1，right=mid-1
   判断条件是目标值和中间值对比，如果不相等，证明这个值即不在中间位置，也不在某一边，那么抛弃某一边的值之外，还要抛弃 mid 的值。
4. 返回值-1 的情况
   这里处理数组为空或者目标值不在数组中，则标记为-1。

左侧边界的二分法

案例：一个数组[1,3,3,3,7,8,10]，查找目标值 3 的最左侧位置。
答案：1

代码

/**
  * 基本二分查找(最左侧)
  * numArray 数组
  * target 目标值
  *
  * @return 目标值的位置，没有匹配到则为-1
  */
fun binaryForTargetLeft(numArray: IntArray, target: Int): Int {
    if (numArray.isEmpty()) {
        return -1
    }
    var left = 0
    var right = numArray.size
    while (left < right) {
        val mid = left + (right - left) / 2 //防止溢出
        when {
            numArray[mid] == target -> {
                right = mid
            }
            numArray[mid] > target -> {
                right = mid
            }
            numArray[mid] < target -> {
                left = mid + 1
            }
        }
    }
    if (left == numArray.size) return -1
    return if (numArray[left] == target) left else -1
}

//目标值的位置是1
WxSolution.binaryForTargetLeft(intArrayOf(1,3,3,3,7,8,10),3)

推导流程

流程图解

细节强调

1. 中间值和目标值一致时 right=mid
   匹配后排除右侧内容，这样可以保证不断靠近左侧边界。

右侧边界的二分法

案例：一个数组[1,2,3,5,7,7,10]，查找目标值 7 的最右侧位置。
答案：5

代码

/**
  * 基本二分查找(最右侧)
  * numArray 数组
  * target 目标值
  *
  * @return 目标值的位置，没有匹配到则为-1
  */
fun binaryForTargetRight(numArray: IntArray, target: Int): Int {
    if (numArray.isEmpty()) {
        return -1
    }
    var left = 0
    var right = numArray.size
    while (left < right) {
        val mid = left + (right - left) / 2 //防止溢出
        when {
            numArray[mid] == target -> {
                left = mid + 1
            }
            numArray[mid] > target -> {
                right = mid
            }
            numArray[mid] < target -> {
                left = mid + 1
            }
        }
    }
    if (left == 0) return -1
    return if (numArray[left - 1] == target) left - 1 else -1
}

//目标值的位置是5
WxSolution.binaryForTargetRight(intArrayOf(1, 2, 3, 5, 7, 7, 10), 7)

推导流程

流程图解

细节强调

1. 中间值和目标值一致时 left=mid+1
   匹配后排除 mid 及左侧内容，这样可以保证不断靠近右侧边界。
2. 跳出循环后判断前一个数据是否是目标值
   因为 left=mid +1，缩小范围的时候可能把目标值的位置也去除了，所以需要判断前一个数据是不是目标值。

时间复杂度

「O(log n)」
二分查找是将循环数组一分为二来执行的。首先 N 变成 N/2，然后又变成 N/4，不断对半，直到找到元素或跳出循环。迭代的最大次数是 log N (base 2) 。

空间复杂度

「O(1)」
通过位置标志进行查找，不需要额外的空间。

项目 github 地址

github.com/ElaineTaylo…

具体写法在项目的 WxSolution 文件中

若帅哥美女对该系列文章感兴趣，可微信搜索公众号（木子闲集）关注更多更新文章哦，谢谢～