【每日一算法】（一）运用排序及二分法解题

暴力解法：
时间复杂度：O(n平方)
双层循环嵌套，每个人都与各个店铺循环比较，取其最小的差值

func minDeviation(personList, shopList []int) (deviationList []int) {
  // 循环去取每个人的位置
  for _, per := range personList {
    // 使用变量记录距离的最小值
    var min int
    for _, shop := range shopList {
      if per == shop {
        // 如果店铺和人之间的距离为0, 那么这个人和店铺的最小距离就是0，同时结束这个人跟店铺的比较，进行下一个人的比较
        deviationList = append(deviationList, 0)
        //将min置为0值, 不然min！=0的话，跳出循环后会将值添加到deviationList中
        min = 0
        // 跳出本次内循环
        break
      } else if per > shop {
        // 如果这个人的坐标大于店铺的坐标
        if min == 0 {
          // 如果min为零，说明是第一次比较，不论per-shop的值是否最小，都赋值给min
          min = per - shop
        } else if min != 0 && per-shop < min {
          // 如果min不得与0 说明不是第一次比较，那么需要比较per-shop的值与min的大小
          min = per - shop
        }
      } else {
        if min == 0 {
          min = shop - per
        } else if min != 0 && shop-per < min {
          min = shop - per
        }
      }
    }
    
    if min == 0 {
      // 如果min==0, 说明本次已经向deviationList中添加过元素， 则跳过下面的追加步骤
      continue
    }
    deviationList = append(deviationList, min)

  }
  return
}

采用二分法+排序：
时间复杂度：O(n*log 2 (m)

func diffList(personList, shopList []int) (deviationList []int) {
  // 由于店铺的位置，是一个无序的列表，如果想使用二分法，则需要将店铺的位置进行排序
  sort.Ints(shopList)
  for _, v := range personList {
    diff := dichotomy(shopList, v)
    deviationList = append(deviationList, diff)
  }
  return
}

func dichotomy(shopList []int, n int) (min int) {
  // 定义两个下标
  left, right := 0, len(shopList)-1
  for left <= right {
    // 每次都取店铺坐标表中的中间的值与这个人的坐标进行比较
    temp := (left + right) / 2
    currentValue := shopList[temp]
    // 如果相等，则代表，距离为0，直接返回最小值为0
    if currentValue == n {
      return 0
    } else if currentValue > n {
      if min == 0 || currentValue-n < min {
        min = currentValue - n
      }
      right = temp - 1
    } else {
      if min == 0 || n-currentValue < min {
        min = n - currentValue
      }
      left = temp + 1
    }
  }
  return
}