算法模板

发表于 | 分类于 ， |

前言

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

二分法

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

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 呢?