66 lines
1.1 KiB
Go
66 lines
1.1 KiB
Go
package search
|
|
|
|
import "log"
|
|
|
|
func BinarySearch(needle int64, haystack []int64) bool {
|
|
defer func() {
|
|
if err := recover(); err != nil {
|
|
log.Printf("%v\n", err)
|
|
return
|
|
}
|
|
}()
|
|
low := 0
|
|
high := len(haystack) - 1
|
|
for low <= high {
|
|
median := (low + high) / 2
|
|
if haystack[median] < needle {
|
|
low = median + 1
|
|
} else {
|
|
high = median - 1
|
|
}
|
|
}
|
|
|
|
if low == len(haystack) || haystack[low] != needle {
|
|
return false
|
|
}
|
|
return true
|
|
}
|
|
|
|
func InterpolationSearch(needed int, haystack []int) bool {
|
|
defer func() {
|
|
if err := recover(); err != nil {
|
|
log.Printf("%v\n", err)
|
|
return
|
|
}
|
|
}()
|
|
if len(haystack) == 0 {
|
|
return false
|
|
}
|
|
|
|
low := 0
|
|
high := len(haystack) - 1
|
|
|
|
for (haystack[low] < needed) && (needed < haystack[high]) {
|
|
if haystack[high] == haystack[low] {
|
|
break
|
|
}
|
|
var mid = low + ((needed-haystack[low])*(high-low))/(haystack[high]-haystack[low])
|
|
|
|
if haystack[mid] < needed {
|
|
low = mid + 1
|
|
} else if haystack[mid] > needed {
|
|
high = mid - 1
|
|
} else {
|
|
return true
|
|
}
|
|
}
|
|
|
|
if haystack[low] == needed {
|
|
return true
|
|
}
|
|
if haystack[high] == needed {
|
|
return true
|
|
}
|
|
return false
|
|
}
|