Algorithm - 二分查找

说明

我们使用有序数组存储键的原因是，第 1 章中作为例子出现的经典二分查找法能够根据数组的索引大大减少每次查找所需的比较次数。我们会使用有序索引数组来标识被查找的键可能存在的子数组的大小范围。在查找时，我们先将被查找的键和子数组的中间键比较。 如果被查找的键小于中间键，我们就在左子数组中继续查找，如果大于我们就在右子数 组中继续查找，否则中间键就是我们要找的键。

Code

实现中有写取巧

package main

import (
	"fmt"
)

// 原始数据类型
type item struct {
	key   string
	value string
}

// 有序数据类型
type indexItem struct {
	item  item
	index int
}

// 有序数组
type list []indexItem

func main() {
	li := make(list, 0)
	li.put(item{key: "m", value: "aa"})
	li.put(item{key: "b", value: "bb"})
	li.put(item{key: "c", value: "bb"})
	li.put(item{key: "e", value: "bb"})
	li.put(item{key: "d", value: "bb"})
	li.put(item{key: "a", value: "bb"})
	li.put(item{key: "a", value: "aa"})
	val, ok := li.get("a")
	fmt.Println(val, ok)
	fmt.Println(li)
	li.delete("o")
	fmt.Println(li)
}

// 删除 key对应的数据
func (lp *list) delete(key string) {
	index := lp.rank(key)
	// 找到了
	if len(*lp) > index && (*lp)[index].item.key == key {
		newSl := make(list, 0)
		newSl = append(newSl, (*lp)[:index]...)
		newSl = append(newSl, (*lp)[index+1:]...)
		newSl.updateIndex(index)
		*lp = newSl
	}
}

// 获取key对应的value
func (lp *list) get(key string) (val string, exist bool) {
	index := lp.rank(key)
	// 找到了
	if len(*lp) > index && (*lp)[index].item.key == key {
		return (*lp)[index].item.value, true
	}
	return "", false
}

// 添加/修改 key对应的数据
func (lp *list) put(i item) {
	length := len(*lp)
	// 不是空数组
	if length > 0 {
		index := lp.rank(i.key)
		if length-1 < index {
			// 添加都最后一位
			*lp = append(*lp, indexItem{item: i, index: index})
			return
		}
		// 找到的index正好是要找的key,直接修改
		if (*lp)[index].item.key == i.key {
			(*lp)[index].item = i
			return
		}
		// 返回的index 不是要的那个key,说明需要在index处插入当前数据
		first, second := (*lp)[:index], (*lp)[index:]
		newSl := make(list, 0)
		newSl = append(newSl, first...)
		newSl = append(newSl, indexItem{item: i, index: index})
		newSl = append(newSl, second...)
		newSl.updateIndex(index)
		*lp = newSl
		return
	}
	// 空数据直接append
	*lp = append(*lp, indexItem{item: i, index: 0})
}

// 找到需要处理的位置
func (lp *list) rank(key string) (index int) {
	length := len(*lp)
	if length > 1 {
		mid := length / 2
		if (*lp)[mid].item.key == key {
			// 中间节点正好是那个key,巧了!
			return (*lp)[mid].index
		}
		var sl list

		if (*lp)[mid].item.key < key {
			// 递归前半部分
			sl = (*lp)[mid:]
		} else {
			// 递归后半部分
			sl = (*lp)[:mid]
		}

		return sl.rank(key)
	}
	// 二分法如果是最后1个的时候
	if key > (*lp)[0].item.key {
		return (*lp)[0].index + 1
	}
	return (*lp)[0].index
}

func (lp *list) updateIndex(i int) {
	for index := i; index < len(*lp); index++ {
		(*lp)[index].index = index
	}
}