GoLang实现的二分查找算法
func BinarySearch(arr *[9]int, val int) int {
return binarySearch(arr, 0, len(arr) - 1, val)
}
func binarySearch(arr *[9]int, leftIndex int, rightIndex int, val int) int {
if leftIndex > rightIndex {
return -1
}
midIndex := (leftIndex + rightIndex) / 2
if (*arr)[midIndex] > val { //中间值大于要查找的值则要查找的值的范围在 leftIndex (midIndex - 1)
return binarySearch(arr, leftIndex, midIndex - 1, val)
} else if (*arr)[midIndex] < val { //中间值小于要查找的值则要查找的值的范围在 (midIndex + 1) rightIndex
return binarySearch(arr, midIndex + 1, rightIndex, val)
} else {
return midIndex
}
}
基于循环的实现
func BinarySearchForLoop(arr *[9]int, val int) int {
leftIndex := 0
rightIndex := len(arr) - 1
for leftIndex <= rightIndex {
midIndex := (leftIndex + rightIndex) / 2
if (*arr)[midIndex] > val { //中间值大于要查找的值则要查找的值的范围在 leftIndex (midIndex - 1)
rightIndex = midIndex - 1
} else if (*arr)[midIndex] < val { //中间值小于要查找的值则要查找的值的范围在 (midIndex + 1) rightIndex
leftIndex = midIndex + 1
} else {
return midIndex
}
}
return -1
}
func main() {
arr := [9]int{1, 2, 3, 4, 5, 6, 7, 8, 9}
index1 := BinarySearch(&arr, 6)
index2 := BinarySearchForLoop(&arr, 6)
fmt.Println(index1, index2)
}