二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
    它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是：（这里假设数组元素呈升序排列）将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止；如 果xa[n/2]，则我们只要在[数组](https://baike.baidu.com/item/%E6%95%B0%E7%BB%84)a的左半部继续搜索x；如果xa[n/2]，则我们只要在数组a的右 半部继续搜索x。

    有序查找时间复杂度为O(n) 二分查找时间复杂度为O(log n)
    swift示例代码：

    1. func testBinary(){
    2.     var pArr:[Person] = []
    3.     for i in 0..<10 {
    4.         let p = Person.init(age: i*2+1)
    5.         pArr.append(p)
    6.     }
    7.     let index = binarySearch(pArr, key: Person.init(age: 13))
    8.     print("index===\(index ?? -1)")
    9. }
    12. ///二分查找
    13. func binarySearch<T: Comparable>(_ a: [T], key: T) -> Int? {
    14.     ///左序号
    15.     var lowerBound = 0
    16.     ///右序号
    17.     var upperBound = a.count
    18.     ///执行逻辑
    19.     while lowerBound < upperBound {
    20.         ///1.计算中间序号 --> n/2
    21.         ///2.取中间序号对应的值 与需要查找的key做比较
    22.         let midIndex = （lowerBound + upperBound） / 2
    23.         if a[midIndex] == key {
    24.             /// 相等则返回对应的序号
    25.             return midIndex
    26.         } else if a[midIndex] < key {
    27.             ///如果middle的值 小于key 则说明key在middle的右边
    28.             ///改变左序号---->从而改变了下次middle对应的序号
    29.             lowerBound = midIndex + 1
    30.         } else {
    31.             ///如果middle的值 大于key 则说明key在middle的左边
    32.             ///改变右序号---->从而改变了下次middle对应的序号
    33.             upperBound = midIndex - 1
    34.         }
    35.     }
    36.     return nil
    37. }
    40. ///有序查找
    41. func sequenceSearch<T: Comparable>(_ a: [T], key: T) -> Int? {
    42.     for i in 0..<a.count {
    43.         if a[i] == key {
    44.             return i
    45.         }
    46.     }
    47.     return nil
    48. }
    50. class Person:Comparable{
    51.     static func < (lhs: Person, rhs: Person) -> Bool {
    52.         return lhs.age < rhs.age
    53.     }
    55.     static func == (lhs: Person, rhs: Person) -> Bool {
    56.         return lhs.age == rhs.age
    57.     }
    59.     static func > (lhs: Person, rhs: Person) -> Bool {
    60.         return lhs.age > rhs.age
    61.     }
    64.     var age:Int = 0
    65.     init(age:Int){
    66.         self.age = age
    67.     }
    68. }