說(shuō)明
二分查找的數(shù)組必須是有序的唐片，二分查找的優(yōu)點(diǎn)是查找操作僅需要O(lgN)時(shí)間串前。
邏輯
首先傳入的數(shù)組必須是有序的宵溅，然后算法開始時(shí)取整個(gè)數(shù)組，并通過(guò)對(duì)比將數(shù)組規(guī)模不停減半肿轨，直到發(fā)現(xiàn)符合尋找條件的元素為止（或者未能找到元素）寿冕。
代碼
package arithmetic
import (
"math"
)
//SearchBinary 二分查找
func SearchBinary(element interface{}, slice []interface{},
funcCondition func(interface{}, interface{}) int) (int, bool) {
var l, r = 0, len(slice) - 1
var i = int((l + r + 1) / 2)
for l != r {
switch funcCondition(slice[i], element) {
case -1: //slice[i] < element
l = i + 1
i = int((l + r + 1) / 2)
continue
case 0: //slice[i] == element
return i, true
case 1: //slice[i] > element
r = i - 1
i = int((l + r + 1) / 2)
continue
}
}
return len(slice), false
}
//InterfaceSearch 搜索接口
type InterfaceSearch interface {
Len() int
Condition(i int, element interface{}) int
GetElement(i int) interface{}
}
//SearchBinaryOop 二分查找 面向?qū)ο?func SearchBinaryOop(element interface{}, slice InterfaceSearch) (int, bool) {
var l, r = 0, slice.Len() - 1
var i = int((l + r + 1) / 2)
for l != r {
switch slice.Condition(i, element) {
case -1: //slice[i] < element
l = i + 1
i = int((l + r + 1) / 2)
continue
case 0: //slice[i] == element
return i, true
case 1: //slice[i] > element
r = i - 1
i = int((l + r + 1) / 2)
continue
}
}
return slice.Len(), false
}
代碼說(shuō)明
面向算法：通過(guò)閉包傳入的判斷條件判斷兩個(gè)元素是否相等，若相等返回元素所在數(shù)組下標(biāo)椒袍，以及true 蚂斤。若不相等，則通過(guò)對(duì)比元素大小槐沼，對(duì)剩余數(shù)組元素取中間下標(biāo)繼續(xù)循環(huán)對(duì)比曙蒸。若最終未搜索到數(shù)據(jù)則返回?cái)?shù)組長(zhǎng)度，以及false岗钩。
面向?qū)ο螅航Y(jié)構(gòu)體通過(guò)實(shí)現(xiàn)接口纽窟，取代原本閉包傳入的方式。
兩種方式各有優(yōu)缺點(diǎn)兼吓。主要在調(diào)用時(shí)臂港，面向算法因?yàn)镚o語(yǔ)言的特性問(wèn)題，需要將結(jié)構(gòu)數(shù)組轉(zhuǎn)換成通用的[]interface{}视搏，此部分比較耗時(shí)审孽。兩種代碼實(shí)現(xiàn)方式都可用于自身結(jié)構(gòu)數(shù)組。其他編程語(yǔ)言情況有所不同浑娜。具體調(diào)用方式見下文佑力。
測(cè)試代碼
package main
import (
"AZframework/arithmetic"
"fmt"
)
//IntSlice []int
type IntSlice []int
func (s IntSlice) Len() int { return len(s) }
func (s IntSlice) Condition(i int, element interface{}) int {
if s[i] == element.(int) {
return 0
}
if s[i] < element.(int) {
return -1
}
return 1
}
func (s IntSlice) GetElement(i int) interface{} { return s[i] }
func main() {
var intB = 2
var sliceC = IntSlice{1, 2, 3, 4, 5, 6}
var interSlice = make([]interface{}, len(sliceC))
for i, d := range sliceC {
interSlice[i] = d
}
var x3, y3 = arithmetic.SearchBinary(intB, interSlice, func(a interface{}, b interface{}) int {
if a.(int) == b.(int) {
return 0
}
if a.(int) < b.(int) {
return -1
}
return 1
})
fmt.Printf("SearchBinary %t %d\n", y3, x3)
var x4, y4 = arithmetic.SearchBinaryOop(intB, sliceC)
fmt.Printf("SearchBinaryOop %t %d\n", y4, x4)
}
日志輸出
SearchBinary true 1
SearchBinaryOop true 1
