算法模板

前言

算法学到一定程度之后,就可以总结出来一套模板了。模板虽好,可没有经过千锤百炼是不可以用得得心应手,信手拈来的。

二分法

用二分法来进行查找,代码模式基本没有什么变化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int BinarySearch(int[] nums, target) {
int start = 0;
int end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] >= target) {
end = mid;
} else {
start = mid + 1;
}
}
if (nums[start] == target) {
return start;
}
if (nums[end] == target) {
return end;
}
return -1;
}

这个模板适用什么问题呢?基本排序数组的二分查找都可以应用。
比如

  • 求排序数组中target第一次(最后)出现的位置
  • 求数组中的峰值
  • 求数组最接近target的值

这个模板是基于查找target出现的第一个位置构建的,其他的问题要对模板进行相应的修改.

怎么修改呢? 先让我对这个模板的几个地方解释一下.

首先是为什么是循环结束的条件是 start + 1 < end 呢?