• 二分查找
• 二叉搜索树
• 合并排序
• 正序数组的中位数
• Huffman 树构造
• Dijkstra 算法
• A* 算法

## 二分查找

### 标准二分查找

class Solution {
public:
int searchInsert(vector<int> &v, int target) {
auto i_hi = v.size() - 1;
auto i_lo = 0;
auto i_md = 0;
while (i_lo != i_hi + 1) {
i_md = i_lo + (i_hi - i_lo) / 2;
if (v[i_md] == target) {
return i_md;
}
if (v[i_md] < target) {
i_lo = i_md + 1;
} else
i_hi = i_md - 1;
}
return i_lo;
}
};


### 寻找上下确界

#include <debug.h>

class Solution {
int binary_search(vector<int> &v, int target) {
auto i_hi = v.size() - 1;
auto i_lo = 0;
auto i_md = 0;
while (i_lo != i_hi + 1) {
i_md = i_lo + (i_hi - i_lo) / 2;
if (v[i_md] == target) {
return i_md;
}
if (v[i_md] < target) {
i_lo = i_md + 1;
} else
i_hi = i_md - 1;
}
return -1;
}
int search_first(vector<int> &v, int target) {
if (v.size() == 0)
return -1;
auto i = binary_search(v, target);
if (i == -1) {
return -1;
}
while (0 <= i - 1 && i - 1 <= v.size() - 1 && v[i - 1] == target) {
i--;
}
return i;
}

int search_last(vector<int> &v, int target) {
if (v.size() == 0)
return -1;
auto i = binary_search(v, target);
if (i == -1) {
return -1;
}
while (0 <= i + 1 && i + 1 <= v.size() - 1 && v[i + 1] == target) {
i++;
}
return i;
}

public:
vector<int> searchRange(vector<int> &nums, int target) {
return {search_first(nums, target), search_last(nums, target)};
}
};

int main(int argc, char const *argv[]) {
Solution s;
vector<int> v = {5, 7, 7, 8, 8, 10};
auto ret = s.searchRange(v, 8);
print_vec(ret);

vector<int> v2 = {1, 2, 3, 3, 3, 2, 1};
auto ret2 = s.searchRange(v2, 3);
print_vec(ret2);

vector<int> v3 = {2, 2};
auto ret3 = s.searchRange(v3, 3);
print_vec(ret3);
return 0;
}


### 终极解法

  int binary_search(vector<int> v, int target) {
int l = -1, r = v.size ();      // 初始条件 l,r 分处边界外。
while (l + 1 != r) {           // 交叉终止
int mid = l + (r - l) / 2;
if (v [mid] <target) {       // 等号有无决定了目标区的左右归属。有等号，则归属左边。
l = mid;
} else {
r = mid;
}
}
return l;                      // 返回的左右对应了分界线的左右
}


class Solution {

public:
// 我们要取得的是 {1, 2, 2, 2, 3} 中的第一个 2
// 那么最后的格局是： {1}{2,2,2,3}，取 r
// 因此 r 的扩张要更强势，即不带等号（等号相当于优先扩张 l）
int search_first(vector<int> &v, int target) {
int l = -1, m, r = v.size();
while (l + 1 != r) {
m = (r - l) / 2 + l;
if (v[m] < target) {
l = m;
} else {
r = m;
}
}
return r;
}
// 我们要取得的是 {1, 2, 2, 2, 3} 中的最后一个 2
// 即最后的格局是 {1,2,2,2}{3}，取 l
// 那么 l 的扩张更强势
int search_last(vector<int> &v, int target) {
int l = -1, m, r = v.size();
while (l + 1 != r) {
m = (r - l) / 2 + l;
// 小于目标值，说明下界给得太小，所以扩张 l
if (v[m] <= target) {
l = m;
} else {
r = m;
}
}
return l;
}

vector<int> searchRange(vector<int> &nums, int target) {
if (nums.empty())
return {-1, -1};

int l = search_first(nums, target);
int r = search_last(nums, target);

bool l_valid = 0 <= l && l <= nums.size() - 1;
if (l_valid && nums[l] != target) {
return {-1, -1};
}

bool r_valid = 0 <= r && r <= nums.size() - 1;
if (r_valid && nums[r] != target) {
return {-1, -1};
}
return {l, r};
}
};



### 练习

35. 搜索插入位置 - 力扣（LeetCode） (leetcode-cn.com)

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode） (leetcode-cn.com)

275. H 指数 II - 力扣（LeetCode） (leetcode-cn.com)

## 二叉搜索树

### 数组转二叉树

108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode） (leetcode-cn.com)


class Solution {
//from, to 左闭右开，即不含 to
TreeNode *slice_to_bst(vector<int> &v, int from, int to) {
if (from == to) {
return nullptr;
}
auto mid = from + (to - from) / 2;
auto left = slice_to_bst(v, from, mid);
auto right = slice_to_bst(v, mid + 1, to);
return new TreeNode(v[mid], left, right);
}

public:
TreeNode *sortedArrayToBST(vector<int> &v) {
return slice_to_bst(v, 0, v.size());
}
};


#include <debug.h>

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right)
: val(x), left(left), right(right) {}
};

void print_indent(int n) {
for (int i = 0; i < n; i++) {
printf(" ");
}
}

void print_tree(TreeNode *t, int ind = 0) {
print_indent(ind);
if (t == nullptr) {
printf("NULL\n");
return;
}
printf("%d\n", t->val);
print_tree(t->left, ind + 2);
print_tree(t->right, ind + 2);
}

class Solution {
//from, to 左闭右开，即不含 to
TreeNode *slice_to_bst(vector<int> &v, int from, int to) {
if (from == to) {
return nullptr;
}
auto mid = from + (to - from) / 2;
auto left = slice_to_bst(v, from, mid);
auto right = slice_to_bst(v, mid + 1, to);
return new TreeNode(v[mid], left, right);
}

public:
TreeNode *sortedArrayToBST(vector<int> &v) {
auto mid = v.size() / 2;
auto left = slice_to_bst(v, 0, mid);
auto right = slice_to_bst(v, mid + 1, v.size());
return new TreeNode(v[mid], left, right);
}
};

int main(int argc, char const *argv[]) {
Solution s;
vector<int> v = {-10, -3, 0, 5, 9};
auto t = s.sortedArrayToBST(v);
print_tree(t);
return 0;
}


## 合并排序（归并排序）

    // v1 = {1, 2, 2, 3, 9，0, 0, 0, 0, 0, 0}
// v2 = {1, 2, 4, 5, 6, 11}

// v1 = {1, 2, 2, 3, 9} v2 = {1, 2, 4, 5, 6, 11}
//                   ^                        ^
//                   l                        r

// v1 = {1, 2, 2, 3, 9，0, 0, 0, 0, 0, 11}
// v1 = {1, 2, 2, 3, 9} v2 = {1, 2, 4, 5, 6, _}
//                   ^                    ^
//                   l                    r

// v1 = {1, 2, 2, 3, _，0, 0, 0, 0, 9, 11}
// v1 = {1, 2, 2, 3, _} v2 = {1, 2, 4, 5, 6, _}
//                ^                       ^
//                l                       r

// v1 = {1, 2, 2, 3, _，0, 0, 0, 6, 9, 11}
// v1 = {1, 2, 2, 3, _} v2 = {1, 2, 4, 5, _, _}
//                ^                    ^
//                l                    r

// v1 = {1, 2, 2, 3, _，0, 0, 5, 6, 9, 11}
// v1 = {1, 2, 2, 3, _} v2 = {1, 2, 4, _, _, _}
//                ^                 ^
//                l                 r

// v1 = {1, 2, 2, 3, _，0, 4, 5, 6, 9, 11}
// v1 = {1, 2, 2, 3, _} v2 = {1, 2, _, _, _, _}
//                ^              ^
//                l              r

// v1 = {1, 2, 2, _, _，3, 4, 5, 6, 9, 11}
// v1 = {1, 2, 2, _, _} v2 = {1, 2, _, _, _, _}
//             ^                 ^
//             l                 r

// v1 = {1, 2, _, 2, 2，3, 4, 5, 6, 9, 11}
// v1 = {1, 2, _, _, _} v2 = {1, _, _, _, _, _}
//          ^                 ^
//          l                 r

// v1 = {1, _, 2, 2, 2，3, 4, 5, 6, 9, 11}
// v1 = {1, _, _, _, _} v2 = {1, _, _, _, _, _}
//       ^                    ^
//       l                    r

// v1 = {1, 1, 2, 2, 2，3, 4, 5, 6, 9, 11}
// v1 = {_, _, _, _, _} v2 = {_, _, _, _, _, _}
//       ^                    ^
//       l                    r


class Solution {
public:
// 初始条件下，v1 的长度是 m+n
void merge(vector<int> &v1, int m, vector<int> &v2, int n) {
int l = m - 1, r = n - 1, ins = m + n - 1; //ins: 插入位置
while (l >= 0 && r >= 0) {
if (v1[l] > v2[r]) {
v1[ins] = v1[l];
ins--;
l--;
} else {
v1[ins] = v2[r];
ins--;
r--;
}
}
// 注意收尾工作。
while (r >= 0) {
v1[ins] = v2[r];
ins--;
r--;
}
}
};


class Solution
{
public:
void merge(vector<int> &nums1, int m, vector<int> &nums2, int n)
{
for (size_t i = 1; i <= m; i++)
{
nums1[m + n - i] = nums1[m - i];
}
int p = 0;
int q = 0;
int sorted = -1;
while (true)
{
if (p == m && q == n)
{
break;
}

if (p == m)
{
nums1[++sorted] = nums2[q];
q++;
continue;
}

if (q == n)
{
nums1[++sorted] = nums1[n + p];
p++;
continue;
}

if (nums1[n + p] <= nums2[q])
{
nums1[++sorted] = nums1[n + p];
p++;
}
else
{
nums1[++sorted] = nums2[q];
q++;
}
}
}
};


class Solution {
int *tmp;

public:
void merge_vec(vector<int> &v, int from, int mid, int to) {
int l = from, r = mid, ins = 0;
while (l < mid && r < to) {
if (v[l] < v[r])
tmp[ins++] = v[l++];
else
tmp[ins++] = v[r++];
}
while (l < mid)
tmp[ins++] = v[l++];

while (r < to)
tmp[ins++] = v[r++];

for (int i = from; i < to; i++)
v[i] = tmp[i - from];
}
void merge_sort(vector<int> &v, int from, int to) {
if (to - from <= 1)
return;
auto mid = from + (to - from) / 2;
merge_sort(v, from, mid);
merge_sort(v, mid, to);
merge_vec(v, from, mid, to);
}
vector<int> sortArray(vector<int> &v) {
tmp = (int *)malloc(v.size() * sizeof(int));
merge_sort(v, 0, v.size());
free(tmp);
return v;
}
};


class Solution {
// 临时存放排序后的升序元素
vector<int> tmp;

public:
void merge_vec(vector<int> &v, int iv1from, int iv1to, int iv2from,
int iv2to) {
// printf("part1 = ");
// print_vec_part(v, iv1from, iv1to);
// printf("part2 = ");
// print_vec_part(v, iv2from, iv2to);

int l = iv1from, r = iv2from, ins = 0; //ins 表示插入位置
while (l < iv1to && r < iv2to) {
// 将较小的复制到 tmp 的开头
if (v[l] < v[r]) {
tmp[ins] = v[l];
l++;
ins++;
} else {
tmp[ins] = v[r];
r++;
ins++;
}
}
// 最后有剩余
while (l < iv1to) {
tmp[ins] = v[l];
l++;
ins++;
}
while (r < iv2to) {
tmp[ins] = v[r];
r++;
ins++;
}
// 将临时元素覆盖 iv1from, iv2to 的 v 的空间
for (int i = iv1from; i < iv2to; i++) {
v[i] = tmp[i - iv1from];
}
// printf("merged [%d,%d] = ", iv1from, iv2to - 1);
// print_vec_part(v, iv1from, iv2to);
}
// 左闭右开
void merge_sort(vector<int> &v, int from, int to) {
if (to - from <= 1) {
return;
}
auto mid = from + (to - from) / 2;
// printf("from = %d\n", from);
// printf("to = %d\n", to);
// printf("mid = %d\n", mid);
merge_sort(v, from, mid);
merge_sort(v, mid, to);
merge_vec(v, from, mid, mid, to);
}
vector<int> sortArray(vector<int> &v) {
tmp = vector<int>(v.size());
merge_sort(v, 0, v.size());
return v;
}
};


### 练习

912. 排序数组 - 力扣（LeetCode） (leetcode-cn.com)

## 正序数组的中位数

[1,2,5,6,13] [3,5,8,12,14,16,18,19]
delete 1,19
[2,5,6,13] [3,5,8,12,14,16,18]
delete 2,18
[5,6,13] [3,5,8,12,14,16]
delete 5,16
[6,13] [3,5,8,12,14]
delete 3,14
[6,13] [5,8,12]
delete 5,13
[6] [8,12]
delete 6,12
med = 8


a =	1,	6,	15,	19,	26,	33,	42,	46,	56,	58,	63,	64,	68,	78,	80,	89,	97,	99,	99
b =	7,	8,	10,	13,	15,	20,	28,	29,	33,	39,	42,	51,	58,	59,	66,	75,	78,	85,	86

a =	1,	6,	15,	19,	26,	33,	42,	46,	56,	58
b =	39,	42,	51,	58,	59,	66,	75,	78,	85,	86

a =	33,	42,	46,	56,	58
b =	39,	42,	51,	58,	59

a =	46,	56,	58
b =	39,	42,	51

a =	46,	56
b =	42,	51

a =	46
b =	51

med = 48.5


a	8,	17,	25,	29,	36,	43,	46,	51,	59,	62,	65,	67,	71,	73,	76,	84,	90,	97
b	2,	4,	11,	15,	25,	31,	41,	46,	55,	57,	65,	74,	76,	79,	80,	89


2,	4,	11,	15,	25,	31,	41,	46,	<>	55,	57,	65,	74,	76,	79,	80,	89


<>	55,	57,	65,	74,	76,	79,	80,	89


a	8,	17,	25,	29,	36,	43,	46,	51,	59,	62
b	55,	57,	65,	74,	76,	79,	80,	89


a	36,	43,	46,	51,	59,	62
b	55,	57,	65,	74


a	46,	51,	59,	62
b	55,	57


a	51,	59
b	55,	57

a
b	55,	57


a = {1, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4}
b = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 4}

a = { 4, 4, 4, 4, 4, 4, 4, }
b = { 1, 1, 1, 1, 1, 1, 1, 1, }


## 哈夫曼树

### 构造哈夫曼树

（1）构造一个全为根的森林，数量为权值的数量。记为 $F$。

（2）在 F 中，选择权最小的两个根，将二者作为左右子树，将二者之和作为根权，构造二叉树。

（3）在 F 中，删除这两棵树，用新的二叉树替代。

【例子】从权值 7,5,5,2,4 的节点构造哈夫曼树。

## Dijkstra 算法

【算法】最短路径查找 —Dijkstra 算法_哔哩哔哩_bilibili

【例子】求下面图 0 到 4 节点的最短路径。

Dijkstra 算法的步骤：

1. 筛选出未访问节点列表 int unvisited []。对于每个 u
1. 找出哪个节点距离出发点最近，即 min_dis [u] 最小值对应的 u
2. 将其标记为访问过 visited [u] = true
2. 筛选出 u 附近的未标记节点 adj_and_unvisited []。对于每个 a
1. 利用 min_dis [u] + dis [u,a] 得到 A 经过 U 到出发点的距离 try_dis
2. 如果 try_dis<min_dis [a]，则 min_dis [a] = a，并更新 prev [a] = u

## A* 算法

### 边界（frontier）

A * 的代价计算公式：

$$整体代价 = 历史代价 + 未来估计代价$$

• 当估计代价变为 0 时，A* 退化为 Dijkstra 算法