二分查找
1称近、二分查找(Binary Search)
二分查找又稱折半查找块攒，它是一種效率較高的查找方法。
二分查找要求：線性表是有序表南蹂，即表中結(jié)點(diǎn)按關(guān)鍵字有序犬金，并且要用向量作為表的存儲結(jié)構(gòu)。不妨設(shè)有序表是遞增有序的六剥。
2晚顷、二分查找的基本思想
二分查找的基本思想是：（設(shè)R[low..high]是當(dāng)前的查找區(qū)間）
（1）首先確定該區(qū)間的中點(diǎn)位置：
（2）然后將待查的K值與R[mid].key比較：若相等，則查找成功并返回此位置疗疟，否則須確定新的查找區(qū)間该默，繼續(xù)二分查找，具體方法如下：
①若R[mid].key>K策彤，則由表的有序性可知R[mid..n].keys均大于K栓袖，因此若表中存在關(guān)鍵字等于K的結(jié)點(diǎn)匣摘，則該結(jié)點(diǎn)必定是在位置mid左邊的子表R[1..mid-1]中，故新的查找區(qū)間是左子表R[1..mid-1]裹刮。
②類似地音榜，若R[mid].key<K，則要查找的K必在mid的右子表R[mid+1..n]中必指，即新的查找區(qū)間是右子表R[mid+1..n]囊咏。下一次查找是針對新的查找區(qū)間進(jìn)行的。
因此塔橡，從初始的查找區(qū)間R[1..n]開始梅割，每經(jīng)過一次與當(dāng)前查找區(qū)間的中點(diǎn)位置上的結(jié)點(diǎn)關(guān)鍵字的比較，就可確定查找是否成功葛家，不成功則當(dāng)前的查找區(qū)間就縮小一半户辞。這一過程重復(fù)直至找到關(guān)鍵字為K的結(jié)點(diǎn)，或者直至當(dāng)前的查找區(qū)間為空(即查找失敗)時為止癞谒。
swift算法實(shí)現(xiàn)
//遞歸
func binary_divide(array:NSMutableArray, low: Int, high:Int, key:Int) -> Int {
print("low=\(low) height=\(high) key=\(key)")
if low > high {
if key > array[low] as! Int {
return low + 1
} else {
return low
}
}
//如果中間值大于目標(biāo)值底燎，說明插入?yún)^(qū)間在 【low，(low + high) / 2 - 1】之間
if array[(low + high)/2] as! Int > key {
return binary_divide(array: array, low: low, high: (low + high) / 2 - 1, key: key)
} else {
//r如果中間值小于目標(biāo)值弹砚，說明區(qū)間在在【(low + high) / 2 + 1双仍，high】
return binary_divide(array: array, low:(low + high) / 2 + 1, high: high, key: key)
}
}
func sort() {
let arrar = NSMutableArray.init(array: [6, 10, 13, 3, 7, 20, 24, 100, 1, 3, 6 ])
for i in 1...(arrar.count-1) {
let key = arrar[i] as! Int
var j = i - 1
//在【0，j-1】區(qū)間利用二分發(fā)找到位置桌吃，之后朱沃，將【position,j-1】之間的元素向右（或者左）移動一位，直到全部排好序
let position = binary_divide(array: arrar, low: 0, high: j, key: key )
while j>=0 && j>=position {
if arrar[j] as! Int > key {
arrar[j + 1] = arrar[j]
}
j = j - 1
}
arrar[position] = key
print(arrar)
print("position = \(position)")
}
}