Swift-二分查找

算法原理

二分查找算法的原理如下：

1. 如果待查序列为空，那么就返回-1，并退出算法；这表示查找不到目标元素。

2. 如果待查序列不为空，则将它的中间元素与要查找的目标元素进行匹配，看它们是否相等。

3. 如果相等，则返回该中间元素的索引，并退出算法；此时就查找成功了。

4. 如果不相等，就再比较这两个元素的大小。

5. 如果该中间元素大于目标元素，那么就将当前序列的前半部分作为新的待查序列；这是因为后半部分的所有元素都大于目标元素，它们全都被排除了。

6. 如果该中间元素小于目标元素，那么就将当前序列的后半部分作为新的待查序列；这是因为前半部分的所有元素都小于目标元素，它们全都被排除了。

7. 在新的待查序列上重新开始第1步的工作。

二分查找之所以快速，是因为它在匹配不成功的时候，每次都能排除剩余元素中一半的元素。因此可能包含目标元素的有效范围就收缩得很快，而不像顺序查找那样，每次仅能排除一个元素

func searchTargetIndex(_ nums:[Int] ,  _ target:Int) -> Int {
    
    // 二分查找的基础 建立在数组为有序数组上，也就是说数组内的数据要从小到大排列
    
    // 定义双指针，begin为0左边下标， end 最后一个下标
    var begin = 0 , end = nums.count - 1
    while begin <= end {
        //取中间下标
        let mid = begin + (end - begin) / 2
        // 如果中间下标小于查找目标值，那么左指针右移 扩大搜索面积
        if nums[mid] < target {
            begin = mid + 1
        }
        // 如果中间下标大于查找目标值，那么右指针左移 缩小搜索面积
        else if nums[mid] > target{
            end = mid - 1
        }
        else{
           return mid
        }
        
    }
    
    return -1
}