算法和题库练习笔记

二分查找（binary search）

尽管二分查找的基本思想相对简单，但细节可以令人难以招架 … — 高德纳

当乔恩·本特利将二分搜索问题布置给专业编程课的学生时，百分之90的学生在花费数小时后还是无法给出正确的解答，主要因为这些错误程序在面对边界值的时候无法运行，或返回错误结果。1988年开展的一项研究显示，20本教科书里只有5本正确实现了二分搜索。不仅如此，本特利自己1986年出版的《编程珠玑》一书中的二分搜索算法存在整数溢出的问题，二十多年来无人发现。Java语言的库所实现的二分搜索算法中同样的溢出问题存在了九年多才被修复。 ——摘自维基百科

视频讲解：二分查找法
时间复杂度：O(logn)
伪代码及方法如下：

力扣相关题目：力扣算法题目704

回溯法（backtracking）

待看做笔记： 使用C++讲解

双指针（Two pointer）

创建两个指针分别指向数组的首、末位置。

//test.c
//利用双指针判断字符的对称问题

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

int main() {
	//设置一个布尔值 symmetry默认为true
	bool symmetry = true;
	char str[]= "BaeAB"; //很明显,该字符串不是对称的
	//遍历字符串数组
	for (int i = 0; i < strlen(str) / 2; i++) {
		//如果对称的两个位置上的数值不相等,则返回false
		if (str[i] != str[strlen(str)-1-i]) {
			printf("%c != %c\n",str[i],str[strlen(str)-1-i]);
			symmetry = false;
			break;
		}
	}
	if (symmetry) {
		printf("%s:该字符串为对称的\n",str);
	} else {
		printf("%s:该字符串不是对称的\n",str);
	}
	return 0;
}

执行程序:

$ gcc test.c 
$ ./a.out 
a != A
BaeAB:该字符串不是对称的

在循环体for中, 当循环第一次时, str[i]和str[strlen(str)-1-i]分别指向str数组的首位和末位元素(这里是指结束符“\0”的前一位元素)。如下图所示: