二分法快速检索数组元素

今天药忘吃喽~ 2022-04-23 08:38 168阅读 0赞

二分法常见的一种算法，可从有序的容器中快速查找到内容

[初识 kotlin 创建一个 kotlinApp][kotlin _ kotlinApp]

[kotlin anko 第一个项目][kotlin anko]

import kotlin.math.abs
    
    object MyTest {
        @JvmStatic
        fun main(arg: Array<String>) {
            var intArray = intArrayOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
            print("fun testForSearch ")
            println("测试查找 5 所在的位置为 ${testForSearch(5, intArray)}\n")
            for (i: Int in 0..intArray.size + 1){
                print("fun testHalfSearch ")
                println("测试查找 $i 所在的位置为 ${testHalfSearch(i, intArray)} \n")
            }
    
        }
        val COMPARE_EQUAL = 0
        val COMPARE_MIN = 1
        val COMPARE_MAX = 2
    
        /**
         * 普通方法查找
         */
        private fun testForSearch (searchData : Int, intArray: IntArray): Int{
            println("查找 $searchData 所在的位置")
                 var item: Int
            for (i in 0..intArray.size) {
                item = intArray[i]
                println("position $i")
                if(searchData == item){
                    println("第 ${i+1} 次计算完成")
                    return i
                }
            }
            return -1
        }
    
        /**
         * 二分法查找某个数据在数据集中的位置
         * @param searchData 需要查找的值
         * @param intArray 从该数组中查找
         * return -1 找不到对应的位置;其他就是 searchData 在 intArray 中的位置
         */
        private fun testHalfSearch (searchData : Int, intArray: IntArray): Int{
            println("查找 $searchData 所在的位置")
            var item: Int // 搜索到的内容
            // 上次检索区域改变的位置【如果从 0 开始 lastSearchChangeRegionPosition 要附初始值 intArray.size，否则相反】
            var lastSearchPosition: Int
            var nextPosition: Int  // 下次要检索的位置
            var halfPosition: Int = intArray.size / 2 // 当前要检索的位置【二分法】
            var searchCount = 0 // 检索次数
            var itemCompare: Int // 当前位置的值与要查找的值比较的状态
            var maxRegion = intArray.size - 1
            var minRegion = 0
            if (searchData == intArray[minRegion]){
                println("最小值第 ${1} 次计算完成")
                return minRegion
            } else if(searchData == intArray[maxRegion]) {
                println("最大值第 ${1} 次计算完成")
                return maxRegion
            }
            do {
                ++ searchCount
                item = intArray[halfPosition]
                itemCompare = if(item > searchData) COMPARE_MAX else if (item < searchData) COMPARE_MIN else COMPARE_EQUAL
                println("本次搜索区域 searchRegion minRegion $minRegion maxRegion $maxRegion")
                when(itemCompare) {
                    COMPARE_MAX->{
                        nextPosition = halfPosition - abs( (halfPosition - minRegion)) / 2
                        if(maxRegion > halfPosition) maxRegion = halfPosition
                    }
                    COMPARE_MIN->{
                        nextPosition = halfPosition + abs(maxRegion - halfPosition) / 2
                        if(minRegion < halfPosition) minRegion = halfPosition
                    }
                    else -> {
                        println("第 ${searchCount} 次计算完成")
                        return halfPosition
                    }
                }
                if (halfPosition == nextPosition) {
                    println("第 ${searchCount} 次计算完成查询不到")
                    break
                }
    
                lastSearchPosition = halfPosition
                halfPosition = nextPosition
    
                println("lastSearchPosition $lastSearchPosition halfPosition $halfPosition " +
                        "nextPosition $nextPosition")
            } while (searchCount < intArray.size)
            return -1
        }
    }
    
    打印测试结果：
    fun testForSearch 不过做过多测试
    
    fun testForSearch 查找 5 所在的位置
    position 0
    position 1
    position 2
    position 3
    position 4
    第 5 次计算完成
    测试查找 5 所在的位置为 4
    
    
    fun testHalfSearch 查找 0 所在的位置
    本次搜索区域 searchRegion minRegion 0 maxRegion 19
    lastSearchPosition 10 halfPosition 5 nextPosition 5
    本次搜索区域 searchRegion minRegion 0 maxRegion 10
    lastSearchPosition 5 halfPosition 3 nextPosition 3
    本次搜索区域 searchRegion minRegion 0 maxRegion 5
    lastSearchPosition 3 halfPosition 2 nextPosition 2
    本次搜索区域 searchRegion minRegion 0 maxRegion 3
    lastSearchPosition 2 halfPosition 1 nextPosition 1
    本次搜索区域 searchRegion minRegion 0 maxRegion 2
    第 5 次计算完成查询不到
    测试查找 0 所在的位置为 -1 
    
    fun testHalfSearch 查找 1 所在的位置
    最小值第 1 次计算完成
    测试查找 1 所在的位置为 0 
    
    fun testHalfSearch 查找 2 所在的位置
    本次搜索区域 searchRegion minRegion 0 maxRegion 19
    lastSearchPosition 10 halfPosition 5 nextPosition 5
    本次搜索区域 searchRegion minRegion 0 maxRegion 10
    lastSearchPosition 5 halfPosition 3 nextPosition 3
    本次搜索区域 searchRegion minRegion 0 maxRegion 5
    lastSearchPosition 3 halfPosition 2 nextPosition 2
    本次搜索区域 searchRegion minRegion 0 maxRegion 3
    lastSearchPosition 2 halfPosition 1 nextPosition 1
    本次搜索区域 searchRegion minRegion 0 maxRegion 2
    第 5 次计算完成
    测试查找 2 所在的位置为 1 
    
    fun testHalfSearch 查找 3 所在的位置
    本次搜索区域 searchRegion minRegion 0 maxRegion 19
    lastSearchPosition 10 halfPosition 5 nextPosition 5
    本次搜索区域 searchRegion minRegion 0 maxRegion 10
    lastSearchPosition 5 halfPosition 3 nextPosition 3
    本次搜索区域 searchRegion minRegion 0 maxRegion 5
    lastSearchPosition 3 halfPosition 2 nextPosition 2
    本次搜索区域 searchRegion minRegion 0 maxRegion 3
    第 4 次计算完成
    测试查找 3 所在的位置为 2 
    
    fun testHalfSearch 查找 4 所在的位置
    本次搜索区域 searchRegion minRegion 0 maxRegion 19
    lastSearchPosition 10 halfPosition 5 nextPosition 5
    本次搜索区域 searchRegion minRegion 0 maxRegion 10
    lastSearchPosition 5 halfPosition 3 nextPosition 3
    本次搜索区域 searchRegion minRegion 0 maxRegion 5
    第 3 次计算完成
    测试查找 4 所在的位置为 3 
    
    fun testHalfSearch 查找 5 所在的位置
    本次搜索区域 searchRegion minRegion 0 maxRegion 19
    lastSearchPosition 10 halfPosition 5 nextPosition 5
    本次搜索区域 searchRegion minRegion 0 maxRegion 10
    lastSearchPosition 5 halfPosition 3 nextPosition 3
    本次搜索区域 searchRegion minRegion 0 maxRegion 5
    lastSearchPosition 3 halfPosition 4 nextPosition 4
    本次搜索区域 searchRegion minRegion 3 maxRegion 5
    第 4 次计算完成
    测试查找 5 所在的位置为 4 
    
    fun testHalfSearch 查找 6 所在的位置
    本次搜索区域 searchRegion minRegion 0 maxRegion 19
    lastSearchPosition 10 halfPosition 5 nextPosition 5
    本次搜索区域 searchRegion minRegion 0 maxRegion 10
    第 2 次计算完成
    测试查找 6 所在的位置为 5 
    
    fun testHalfSearch 查找 7 所在的位置
    本次搜索区域 searchRegion minRegion 0 maxRegion 19
    lastSearchPosition 10 halfPosition 5 nextPosition 5
    本次搜索区域 searchRegion minRegion 0 maxRegion 10
    lastSearchPosition 5 halfPosition 7 nextPosition 7
    本次搜索区域 searchRegion minRegion 5 maxRegion 10
    lastSearchPosition 7 halfPosition 6 nextPosition 6
    本次搜索区域 searchRegion minRegion 5 maxRegion 7
    第 4 次计算完成
    测试查找 7 所在的位置为 6 
    
    fun testHalfSearch 查找 8 所在的位置
    本次搜索区域 searchRegion minRegion 0 maxRegion 19
    lastSearchPosition 10 halfPosition 5 nextPosition 5
    本次搜索区域 searchRegion minRegion 0 maxRegion 10
    lastSearchPosition 5 halfPosition 7 nextPosition 7
    本次搜索区域 searchRegion minRegion 5 maxRegion 10
    第 3 次计算完成
    测试查找 8 所在的位置为 7 
    
    fun testHalfSearch 查找 9 所在的位置
    本次搜索区域 searchRegion minRegion 0 maxRegion 19
    lastSearchPosition 10 halfPosition 5 nextPosition 5
    本次搜索区域 searchRegion minRegion 0 maxRegion 10
    lastSearchPosition 5 halfPosition 7 nextPosition 7
    本次搜索区域 searchRegion minRegion 5 maxRegion 10
    lastSearchPosition 7 halfPosition 8 nextPosition 8
    本次搜索区域 searchRegion minRegion 7 maxRegion 10
    第 4 次计算完成
    测试查找 9 所在的位置为 8 
    
    fun testHalfSearch 查找 10 所在的位置
    本次搜索区域 searchRegion minRegion 0 maxRegion 19
    lastSearchPosition 10 halfPosition 5 nextPosition 5
    本次搜索区域 searchRegion minRegion 0 maxRegion 10
    lastSearchPosition 5 halfPosition 7 nextPosition 7
    本次搜索区域 searchRegion minRegion 5 maxRegion 10
    lastSearchPosition 7 halfPosition 8 nextPosition 8
    本次搜索区域 searchRegion minRegion 7 maxRegion 10
    lastSearchPosition 8 halfPosition 9 nextPosition 9
    本次搜索区域 searchRegion minRegion 8 maxRegion 10
    第 5 次计算完成
    测试查找 10 所在的位置为 9 
    
    fun testHalfSearch 查找 11 所在的位置
    本次搜索区域 searchRegion minRegion 0 maxRegion 19
    第 1 次计算完成
    测试查找 11 所在的位置为 10 
    
    fun testHalfSearch 查找 12 所在的位置
    本次搜索区域 searchRegion minRegion 0 maxRegion 19
    lastSearchPosition 10 halfPosition 14 nextPosition 14
    本次搜索区域 searchRegion minRegion 10 maxRegion 19
    lastSearchPosition 14 halfPosition 12 nextPosition 12
    本次搜索区域 searchRegion minRegion 10 maxRegion 14
    lastSearchPosition 12 halfPosition 11 nextPosition 11
    本次搜索区域 searchRegion minRegion 10 maxRegion 12
    第 4 次计算完成
    测试查找 12 所在的位置为 11 
    
    fun testHalfSearch 查找 13 所在的位置
    本次搜索区域 searchRegion minRegion 0 maxRegion 19
    lastSearchPosition 10 halfPosition 14 nextPosition 14
    本次搜索区域 searchRegion minRegion 10 maxRegion 19
    lastSearchPosition 14 halfPosition 12 nextPosition 12
    本次搜索区域 searchRegion minRegion 10 maxRegion 14
    第 3 次计算完成
    测试查找 13 所在的位置为 12 
    
    fun testHalfSearch 查找 14 所在的位置
    本次搜索区域 searchRegion minRegion 0 maxRegion 19
    lastSearchPosition 10 halfPosition 14 nextPosition 14
    本次搜索区域 searchRegion minRegion 10 maxRegion 19
    lastSearchPosition 14 halfPosition 12 nextPosition 12
    本次搜索区域 searchRegion minRegion 10 maxRegion 14
    lastSearchPosition 12 halfPosition 13 nextPosition 13
    本次搜索区域 searchRegion minRegion 12 maxRegion 14
    第 4 次计算完成
    测试查找 14 所在的位置为 13 
    
    fun testHalfSearch 查找 15 所在的位置
    本次搜索区域 searchRegion minRegion 0 maxRegion 19
    lastSearchPosition 10 halfPosition 14 nextPosition 14
    本次搜索区域 searchRegion minRegion 10 maxRegion 19
    第 2 次计算完成
    测试查找 15 所在的位置为 14 
    
    fun testHalfSearch 查找 16 所在的位置
    本次搜索区域 searchRegion minRegion 0 maxRegion 19
    lastSearchPosition 10 halfPosition 14 nextPosition 14
    本次搜索区域 searchRegion minRegion 10 maxRegion 19
    lastSearchPosition 14 halfPosition 16 nextPosition 16
    本次搜索区域 searchRegion minRegion 14 maxRegion 19
    lastSearchPosition 16 halfPosition 15 nextPosition 15
    本次搜索区域 searchRegion minRegion 14 maxRegion 16
    第 4 次计算完成
    测试查找 16 所在的位置为 15 
    
    fun testHalfSearch 查找 17 所在的位置
    本次搜索区域 searchRegion minRegion 0 maxRegion 19
    lastSearchPosition 10 halfPosition 14 nextPosition 14
    本次搜索区域 searchRegion minRegion 10 maxRegion 19
    lastSearchPosition 14 halfPosition 16 nextPosition 16
    本次搜索区域 searchRegion minRegion 14 maxRegion 19
    第 3 次计算完成
    测试查找 17 所在的位置为 16 
    
    fun testHalfSearch 查找 18 所在的位置
    本次搜索区域 searchRegion minRegion 0 maxRegion 19
    lastSearchPosition 10 halfPosition 14 nextPosition 14
    本次搜索区域 searchRegion minRegion 10 maxRegion 19
    lastSearchPosition 14 halfPosition 16 nextPosition 16
    本次搜索区域 searchRegion minRegion 14 maxRegion 19
    lastSearchPosition 16 halfPosition 17 nextPosition 17
    本次搜索区域 searchRegion minRegion 16 maxRegion 19
    第 4 次计算完成
    测试查找 18 所在的位置为 17 
    
    fun testHalfSearch 查找 19 所在的位置
    本次搜索区域 searchRegion minRegion 0 maxRegion 19
    lastSearchPosition 10 halfPosition 14 nextPosition 14
    本次搜索区域 searchRegion minRegion 10 maxRegion 19
    lastSearchPosition 14 halfPosition 16 nextPosition 16
    本次搜索区域 searchRegion minRegion 14 maxRegion 19
    lastSearchPosition 16 halfPosition 17 nextPosition 17
    本次搜索区域 searchRegion minRegion 16 maxRegion 19
    lastSearchPosition 17 halfPosition 18 nextPosition 18
    本次搜索区域 searchRegion minRegion 17 maxRegion 19
    第 5 次计算完成
    测试查找 19 所在的位置为 18 
    
    fun testHalfSearch 查找 20 所在的位置
    最大值第 1 次计算完成
    测试查找 20 所在的位置为 19 
    
    fun testHalfSearch 查找 21 所在的位置
    本次搜索区域 searchRegion minRegion 0 maxRegion 19
    lastSearchPosition 10 halfPosition 14 nextPosition 14
    本次搜索区域 searchRegion minRegion 10 maxRegion 19
    lastSearchPosition 14 halfPosition 16 nextPosition 16
    本次搜索区域 searchRegion minRegion 14 maxRegion 19
    lastSearchPosition 16 halfPosition 17 nextPosition 17
    本次搜索区域 searchRegion minRegion 16 maxRegion 19
    lastSearchPosition 17 halfPosition 18 nextPosition 18
    本次搜索区域 searchRegion minRegion 17 maxRegion 19
    第 5 次计算完成查询不到
    测试查找 21 所在的位置为 -1

测试结果显而易见。算法的强大。

[kotlin _ kotlinApp]: https://blog.csdn.net/ff_hh/article/details/79925636
[kotlin anko]: https://blog.csdn.net/ff_hh/article/details/85160405