Swift 二分查找带print

binarySearch.swift

func countOccurrencesOfKey(_ key: Int, inArray a: [Int]) -> Int {
	func leftBoundary() -> Int {
		print("---------------")
		var low = 0
		var high = a.count
		var index = 0
		while low < high {
			index += 1
			print("左边界第\(index)次查找")
			let midIndex = low + (high - low)/2
			
			print("--划分范围后的数组：\(a[low..<high])")
			print("--索引为\(midIndex)的中间键：\(a[midIndex])")
			print("--查找范围：\(low..<high)")
			if a[midIndex] < key {
				low = midIndex + 1
			} else {
				high = midIndex
			}
		}
		print("low值为：\(low)")
		return low
	}
	
	func rightBoundary() -> Int {
		var low = 0
		var high = a.count
		var index = 0
		while low < high {
			index += 1
			print("右边界第\(index)次查找")
			let midIndex = low + (high - low)/2
			print("--划分范围后的数组：\(a[low..<high])")
			print("--索引为\(midIndex)的中间键：\(a[midIndex])")
			print("--查找范围：\(low..<high)")
			if a[midIndex] > key {
				high = midIndex
			} else {
				low = midIndex + 1
			}
		}
		print("low值为：\(low)")
		return low
	}
	
	return rightBoundary() - leftBoundary()
}

let a = [ 0, 1, 1, 3, 3, 3, 3, 6, 8, 10, 11, 11 ]

print(countOccurrencesOfKey(3, inArray: a) )

//右边界第1次查找
//--划分范围后的数组：[0, 1, 1, 3, 3, 3, 3, 6, 8, 10, 11, 11]
//--索引为6的中间键：3
//--查找范围：0..<12
//右边界第2次查找
//--划分范围后的数组：[6, 8, 10, 11, 11]
//--索引为9的中间键：10
//--查找范围：7..<12
//右边界第3次查找
//--划分范围后的数组：[6, 8]
//--索引为8的中间键：8
//--查找范围：7..<9
//右边界第4次查找
//--划分范围后的数组：[6]
//--索引为7的中间键：6
//--查找范围：7..<8
//low值为：7
//---------------
//左边界第1次查找
//--划分范围后的数组：[0, 1, 1, 3, 3, 3, 3, 6, 8, 10, 11, 11]
//--索引为6的中间键：3
//--查找范围：0..<12
//左边界第2次查找
//--划分范围后的数组：[0, 1, 1, 3, 3, 3]
//--索引为3的中间键：3
//--查找范围：0..<6
//左边界第3次查找
//--划分范围后的数组：[0, 1, 1]
//--索引为1的中间键：1
//--查找范围：0..<3
//左边界第4次查找
//--划分范围后的数组：[1]
//--索引为2的中间键：1
//--查找范围：2..<3
//low值为：3