1 func binarySearch(nodes []*node, word Text) (int, bool) { 2 start := 0 3 end := len(nodes) - 1 4 5 // 特例: 6 if len(nodes) == 0 { 7 // 当slice为空时,插入第一位置 8 return 0, false 9 } 10 compareWithFirstWord := bytes.Compare(word, nodes[0].word) 11 if compareWithFirstWord < 0 { 12 // 当要查找的元素小于首元素时,插入第一位置 13 return 0, false 14 } else if compareWithFirstWord == 0 { 15 // 当首元素等于node时 16 return 0, true 17 } 18 compareWithLastWord := bytes.Compare(word, nodes[end].word) 19 if compareWithLastWord == 0 { 20 // 当尾元素等于node时 21 return end, true 22 } else if compareWithLastWord > 0 { 23 // 当尾元素小于node时 24 return end + 1, false 25 } 26 27 // 二分 28 current := end / 2 29 for end-start > 1 { 30 compareWithCurrentWord := bytes.Compare(word, nodes[current].word) 31 if compareWithCurrentWord == 0 { 32 return current, true 33 } else if compareWithCurrentWord < 0 { 34 end = current 35 current = (start + current) / 2 36 } else { 37 start = current 38 current = (current + end) / 2 39 } 40 } 41 return end, false 42 }
有疑问加站长微信联系(非本文作者)