​ 二分查找算法也称为折半搜索、二分搜索，是一种在有序数组中查找某一特定元素的搜索算法。算法是建立在有序数组基础上的。时间复杂度： T(n) = Θ(logn)。

原理及实现

基本原理：使用递归、分治的思想

  • ① 当数组为空时，说明数组中不存在需查找的元素。
  • ② 用有序数组的中间位置元素与需查找元素进行大小比较，如果相等，则查找结束。
  • ③ 如果中间位置元素大于需查找元素，则从数组左侧位置进行递归查找。
  • ④ 如果中间位置元素小于需查找元素，则从数组右侧位置进行递归查找。

使用Swift编写简单的代码实现，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 *  二分查找
 * 使用递归、分治的思想
 * ① 当数组为空时，说明数组中不存在需查找的元素。
 * ② 用有序数组的中间位置元素与需查找元素进行大小比较，如果相等，则查找结束。
 * ③ 如果中间位置元素大于需查找元素，则从数组左侧位置进行递归查找。
 * ④ 如果中间位置元素小于需查找元素，则从数组右侧位置进行递归查找。
 **/

func binarySearch<T:Comparable>(array:Array<T>, start:Int, end:Int, value:T) -> Int{
    let count = end - start + 1;
    if count <= 0 {
        return -1;//没有查找到
    }
    let midIndex = (start + end) / 2;
    let midValue = array[midIndex];
    if midValue > value {//在左侧查找
        return binarySearch(array: array, start: start, end: midIndex - 1, value: value);
    }else if midValue < value {//在右侧查找
        return binarySearch(array: array, start: midIndex + 1, end: end, value: value);
    }else{//位置查找到，即当前数组中间位置元素
        return midIndex;
    }
}

测试用例及结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//方法调用
func callBinarySearch<T:Comparable>(array: Array<T>, value:T){
    
    let index = binarySearch(array: array, start: 0, end: array.count - 1, value: value);
    
    print("Index Of Value \(value)  In Array \(array) is : \(index)")
    
}

var intArray =  [1, 4, 7, 8, 9, 11, 11, 15, 16, 24];
callBinarySearch(array: intArray , value: 3)
callBinarySearch(array: intArray , value: 16)

var stringArray =  ["Assembly", "BASIC", "C#", "Java", "Objective-C", "PHP", "Swift"];
callBinarySearch(array: stringArray,value:"Assembly")
callBinarySearch(array: stringArray,value:"PHP")
callBinarySearch(array: stringArray,value:"AAA")


//程序输出
Index Of Value 3  In Array [1, 4, 7, 8, 9, 11, 11, 15, 16, 24] is : -1
Index Of Value 16  In Array [1, 4, 7, 8, 9, 11, 11, 15, 16, 24] is : 8
Index Of Value Assembly  In Array ["Assembly", "BASIC", "C#", "Java", "Objective-C", "PHP", "Swift"] is : 0
Index Of Value PHP  In Array ["Assembly", "BASIC", "C#", "Java", "Objective-C", "PHP", "Swift"] is : 5
Index Of Value AAA  In Array ["Assembly", "BASIC", "C#", "Java", "Objective-C", "PHP", "Swift"] is : -1