使用二分查找前提:数组已经排序(因为查找的是索引,索引递增还是递减无所谓)

核心:通过比较target值与中间值的大小,来更改左右两边的索引值,来缩小范围

注意:需要考虑到当数字有重复时, 是否返回任意一个数的下标即可

while循环版本

public class func binarySearch(target: Int,sourceList: [Int]) -> Int {

    var start: Int = 0
    var end: Int = sourceList.count-1
    
    while start <= end {
        let middle = (start + end)/2
        // 如果中值等于目标值,直接返回中值index
        if target == sourceList[middle] {
            return middle
        }
        
        // 如果目标小于中值.说明在前半段
        if target < sourceList[middle] {
            end = middle - 1
        }
        
        // 如果目标大于中值.说明在后半段
        if target > sourceList[middle] {
            start = middle + 1
        }
    }
    return -1
}

递归版本

public class func binarySearch2(target: Int,sourceList: [Int]) -> Int {
    
    let res = BinarySearchInternal(target: target, startIndex: 0, endIndex: sourceList.count-1, sourceList: sourceList)
    return res
}

public class func binarySearchInternal(target: Int,startIndex: Int,endIndex: Int, sourceList: [Int]) -> Int {

    if startIndex > endIndex {
        return -1
    }
    let middle = (startIndex + startIndex)/2
    // 如果中值等于目标值,直接返回中间值index
    if target == sourceList[middle] {
        return middle
    }
    
    // 如果目标小于中间值.说明在前半段
    if target < sourceList[middle] {
        return BinarySearchInternal(target: target, startIndex: startIndex, endIndex: middle - 1, sourceList: sourceList)
    }else { // 如果目标大于中间值.说明在后半段
        return BinarySearchInternal(target: target, startIndex: middle + 1, endIndex: endIndex, sourceList: sourceList)
    }
}

二分查找时间复杂度为O(log n)

查找第一个大于或等于某个数的下标(有序数组)

// 查找第一个大于或等于某个数的下标
public class func binarySearchGreatOrEqual(target: Int,sourceList: [Int]) -> Int {
    
    var start: Int = 0
    var end: Int = sourceList.count-1
    // 默认未找到为-1
    var result : Int = -1
    
    while start <= end {
        let middle = (start + end)/2
        
        print("middleIndex=\(middle)")
        print("middleValue=\(sourceList[middle])")
        if target <= sourceList[middle] {
            end = middle - 1
            result = middle
            print("end=\(end)")
        }else {
            start = middle + 1
            print("start=\(start)")
        }
        print("------------")
    }
    print("start=\(start),end=\(end)")
    return result
}

测试target=1,5,6,8,9都没问题

// let numbersArray = [1, 4, 6, 6, 8]
let numbersArray = [1, 4, 6, 7, 8]
let index = BinarySearch.binarySearchGreatOrEqual(target: 1, sourceList: numbersArray)
print(index)