MergeSort/BinarySearch

#归并排序/MergeSort

```

//有序的合并l两个数组

func merge<Int>(left:[Int], right:[Int])->[Int] {

var a = [Int]()

a.append(contentsOf: left)

a.append(contentsOf: right)

print(a)

return a

}

//采用递归按照二叉树的方式逐步实现左右递归合并

func mergeSort( array:[Int])->[Int]{

if array.isEmpty || array.count == 1 {

return array

}

let middle = array.count/2

let left = mergeSort(array:Array( array[0 ..< middle]))

let right = mergeSort(array:Array(array[middle ..< array.count]))

let value = merge(left: left, right: right)

return value

}

print(mergeSort(array: [12,4,23,534,3]))

```

merge 算法跟数据的是否有序无关，都要将每个数据遍历一遍才能达到排序的目的

其思想是分而治之逐渐有序，先拆分然后，卓段排序然后逐渐拼接合并，最终整体有序

#折半查找/BinarySearch

**折半查找是有查找前提的：序列必须有序 效率为log2(n)**

对于折半查找有个很有趣的故事：

从A城到B城架设的电线，电路突然中断需要查找故障，那么要怎么查呢？当然是要爬电线杆了。可是电线杆有那么多？怎么找呢？一根根的爬上去找是不可能的。于是乎只能```折半查找啦```

```

逗逼一下方法名：

func zheban<T>( source:[T] = [], dest:T)->T? where T:Comparable{

if source.isEmpty {

return nil

}

if source.count == 1 {

if source[0] == dest {

return source[0]

}

return nil

}

let middleIndex = source.count / 2

if middleIndex == source.count {

return nil

}

print("\(source) => \(dest)")

let value = source[middleIndex]

if value == dest {

return value

}else if value < dest { //< 向后搜索

return zheban(source: Array(source[middleIndex ..< source.count]), dest: dest)

}else{

return zheban(source: Array(source[0 ..< middleIndex ]), dest: dest)

}

}

print(zheban(source: [1,2,4,54,55,66,100], dest: 101))

print(zheban(source: ["A","B", "C","F"], dest: "C"))

```

!