Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Swift 二分查找带print
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.