查找算法

Posted on Edited on In Views:
在日常工作中很多时候查询一个数组中的某个值，或者第多大的值，需要用到查找算法，有的查找算法前提是做好了排序，有的没有，这里对常用的算法做一个归纳。

在日常工作中很多时候查询一个数组中的某个值，需要用到查找算法，有的查找算法前提是做好了排序，有的没有，这里对常用的算法做一个归纳。

二分法

二分法的思想是每次查询都排除掉一半。使用二分法需要注意已经做好了排序。

首尾作为二分的首尾，将目标值和中间值比较，比较之后，将范围缩小，将中值作为首或者尾，缩小成首为中值+1或者尾为中值-1，当首不大于尾进行循环判断。

1
2
3
4
5
6
7
8
9
10
11
12
start, end := 0, len(s)-1
for start <= end {
    mid := (start + end) / 2
    if s[mid] < target {
        start = mid + 1
    } else if s[mid] > target {
        end = mid - 1
    } else {
        return mid
    }
}
return -1

拉格朗日中值查找

拉格朗日中值查找法的思想建立在二分法的思想上，二分法是平均分配，拉格朗日是按照查询的数字按照比例分配。

这个比例是值大小和尾部大小的差比头尾大小的差

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
if s[0] > target || s[len(s)-1] < target {
    return -1
}
start, end := 0, len(s)-1
for start <= end {
    mid := start + int(float64(target-s[start])/float64(s[end]-s[start])*float64(end-start))
    fmt.Println(mid)
    if s[mid] < target {
        start = mid + 1
    } else if s[mid] > target {
        end = mid - 1
    } else {
        return mid
    }
}
return -1

核心改动：取值的比例，通过值的比例判断索引跳跃的比例。

1
mid := start + int(float64(target-s[start])/float64(s[end]-s[start])*float64(end-start))

在一大堆的数字中，查找第n大的数字

首先，如果直接排序，无论是使用冒泡、快排、堆排，都可以先将局部数据进行排序，然后进行对比。例如冒泡，则需要排n次，如果是快排，则全员排序，如果是堆排，则创建k个数字的堆，后续数字与堆顶比较。这里介绍另外一种方式，也就是分而治之的思想。

当需要解决的问题非常非常大时，面向的情况多、数据量大，则需要使用到分而治之的思想，也就是以大化小，处理小的数字。

  1. 先将一堆数字按照一定的范围区分，例如区分1-100,101-200,201-300，便利所有文件，将文件区分成个数比较少的一堆数字
  2. 目的堆中数字的个数在可接受范围内，则使用排序算法排序这堆数据
  3. 如果目的堆中的数字也非常多，则回到1中，再次拆分范围