数据结构

查找

折半查找

1. 复杂度：O(logn)

2. 对象：排序的数组

3. 内容：

   • 设置高低指针
   • 中间开始，如果值相等则结束
   • 值不相等，高低指针向中间迫近
   • 指针相遇，结束

4. 实现

   func BinarySearch(arr []int, goal int) int {
       // 取高低索引
       low, high := 0, len(arr)-1
       // 指针未相遇的时候循环
       for low <= high {
           mid := low + (high-low)>>1
           midV := arr[mid]
           // 符合条件，返回索引
           if midV == goal {
               return mid
           }
           // 不符合条件，高低指针向中间迫近
           if midV < goal {
               low = mid + 1
           } else {
               high = mid - 1
           }
       }
       return -1
   }
   

排序

快速排序

x s

插入排序