golang实现算法(1)-二分查找

2018-03-26 21:57:17 admin ...

二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。

算法时间O(log(n))

满足条件:

1.必须采用顺序存储结构。
2.必须按关键字大小有序排列。

/************************************************************
** @Description: binary_search 二分查找法
** @Author: haodaquan
** @Date:   2018-03-25 23:33
** @Last Modified by:   haodaquan
** @Last Modified time: 2018-03-25 23:33
*************************************************************/
package main
import (
   "fmt"
)
func main() {
   a := []int{0, 1, 2, 3, 4, 5, 6}
   mid := binary(a, -4)
   fmt.Println(mid)
}
func binary(s []int, search int) int {
   left, right, mid := 0, len(s)-1, 0
   for {
      if s[mid] > search {
         right = mid - 1
         mid = (left + right) / 2
      } else if s[mid] == search {
         break
      } else {
         left = mid + 1
         mid = (left + right) / 2
      }
      if right < left {
         mid = -1
         break
      }
   }
   return mid
}

相似文章


345708673

在路上

技术无止境,一直在路上。 年过而立,惴惴不安,愈加发奋,孜孜求学。