Swift - 二分查找算法_app

概述醒脑图 ,给我自己看的思想顾名思义,二分查找就是将数组每次劈开一半,分为两个部分,然后判断需要查找的数据在那一部分,再对这部分数据劈开一半,如此重复...。二分查找算法要求待查数组为有序数组。步骤假设待查数据源list是一个有序数组1. 确定待查数组或子数组的开始位置start(每次递归会根据情况变化)2. 确定待查数组或子数组的结束位置end(每次递归会根据情况变化)3. 确定待查

醒脑图,给我自己看的

思想

顾名思义,二分查找就是将数组每次劈开一半,分为两个部分,然后判断需要查找的数据在那一部分,再对这部分数据劈开一半,如此重复...。二分查找算法要求待查数组为有序数组。

步骤

假设待查数据源List是一个有序数组1. 确定待查数组或子数组的开始位置start(每次递归会根据情况变化)2. 确定待查数组或子数组的结束位置end(每次递归会根据情况变化)3. 确定待查数组的中值位置mIDdle = (start + end)/2 (每次递归会根据情况变化)4. 递归上面的 *** 作,结束条件为start和end重合,如果找了整个数组都没有这个结果,返回-1,结束递归

看下面代码中的注释吧,清晰明了

代码

import UIKit@H_404_16@var str = "Hello,man"@H_404_16@var List = [Int]()//待查随机模拟数组@H_404_16@var item = 0//造一个有十个元素的模拟数据数组@H_404_16@for i @H_404_16@in 0..<10 {    item = item + Int(arc4random_uniform(UInt32(20)));    List.append(item)}//随机一个元素@H_404_16@let targetNum = List[Int(arc4random_uniform(UInt32(10)))]print("原始数组为: \(List) 目标数字为: \(targetNum)")//compareTimes : 记录比较次数@H_404_16@var compareTimes = 0//result : 记录结果@H_404_16@var result = binarySearch(targetNum,List)print("搜索结果: \(result) 比较次数 : \(compareTimes)")/// 二分查找法////// - Parameters:/// - targetNum: 目标数字/// - sourceList: 原始数组/// - Returns: 目标数值在原始数组中的位置func binarySearch(_ targetNum:Int,_ sourceList:[Int]) -> Int{    @H_404_16@var start = 0    @H_404_16@var end = sourceList.count - 1    //只要没有指向同一个数,则继续查找    @H_404_16@while start <= end {        compareTimes += 1        //取中值        @H_404_16@var mIDdle = (start + end)/2        print("----第\(compareTimes)次比较的中值为\(sourceList[mIDdle])")        //如果中值等于目标值,直接返回中值index        @H_404_16@if targetNum == sourceList[mIDdle] {            @H_404_16@return mIDdle        }        //如果目标小于中值.说明在前半段        @H_404_16@if targetNum < sourceList[mIDdle] {            end = mIDdle - 1        }        //如果目标大于中值.说明在后半段        @H_404_16@if targetNum > sourceList[mIDdle] {            start = mIDdle + 1        }    }    //没有找到    @H_404_16@return -1}