算法篇：二分查找基础篇

目标Target:需要查找的值
索引index:要查找的当前位置
左右指示符Left,Right:用来维持查找的空间坐标
中间指示符Mid:用应用条件来确定我们应该向左查找还是向右查找的索引 

二分查询，步骤：
1.预处理过程（绝大部分是对未排序的数据进行排序）
2.二分查找过程（找到合适的循环条件，第一次将查找空间一分为二）
3.后处理过程（在剩余的空间中，找到合适的目标值）

模型：
1.初始条件：left=0,right=length-1
2.终止条件：left>right
3.向左查找：right = mid -1 
4.向右查找：left = mid+1
适用的题目：在递增递减区间中搜索目标值；
一般有三类：找特定值，
找大于特定的元素（上界），
找小于特定值的元素（下界）

func search(nums []int, target int) int {
  l,r := 0, len(nums)-1
  for l<=r {
      // 小技巧：这种方式等同于（l+r）/2，如此实现防止r+l超过int的最大值
      m := l+ (r-l)/2 
      if target == nums[m] {
          return m
      }
      if target > nums[m] {
          l = m+1
      } else {
          r = m-1
      }
  }
  return -1
}

func minEatingSpeed(piles []int, H int) int {
    var max int 
    for _, p := range piles {
        if p > max {
            max = p
        }
    }
    left, right := 1, max
    for left < right {
        mid := left + (right - left)/2
        if isEnable(piles, mid, H) { // 表示吃的太慢了，需要让她吃的快一点
            left = mid +1
        } else { // 表示吃的太快了，需要让她慢点吃
            right = mid  
        }
    }
    return left 
}
func isEnable(piles []int, speed, H int) bool {
    sum := 0 
    for _,p:= range piles{
        sum += (p+speed-1)/speed
    }
    return sum>H
}
/*
算法：该问题转化为她按照最慢速度和最快速度之间，找到恰好时间==H的那个速度。
二分查找
*/

func mySqrt(x int) int {
    if x==0 {
        return 0
    }
    
    left,right := 1,x/2
    
    for left<right { // [1,x/2]范围内都遍历结束，二分法就能找到这个平方根
        mid := (left + right + 1) >> 1
        squar := mid*mid
        if squar > x{ // 平方大于x，移动right到右中位数，平方根要在左侧
            right = mid-1
        } else { // 平方小于x,移动left到右中位数，平方根要在右侧
            left = mid
        }
    }
    return left
}
/*
平方根的求解算法：
可以转化成二分查找法，左边界是1,右边界是x/2.
判断条件是：平方根mid的平方>x,就向左偏移，小于x的话就往有偏移。
直到数字区间变成1的时候，就是这个平方根了。
*/