题目：
假如有一家连锁店，6个店铺的位置坐标分别是[5, 2, 3, 9, 10, 7]
现在有6个人，坐标位置分别是[3, 6, 4, 15, 20, 8]
求每个人距离店铺的最短距离
如上题，答案是[0, 1, 1, 5, 10, 1]
解题思路（一）
暴力解法：
时间复杂度：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
}
分享
