一. 初识算法
1.1 什么是算法？
在数学和计算机科学领域，算法是一系列有限的严谨指令，通常用于解决一类特定问题或执行计算
不正式的说，算法就是任何定义优良的计算过程：接收一些值作为输入，在有限的时间内，产生一些值作为输出。
1.2 什么是数据结构？
在计算机科学领域，数据结构是一种数据组织、管理和存储格式，通常被选择用来高效访问数据
数据结构是一种存储和组织数据的方式，旨在便于访问和修改
1.3 衡量算法好坏
一般从以下维度来评估算法的优劣：正确性、可读性、健壮性（对不合理输入的反应能力和处理能力）。
时间复杂度（time complexity）：估算程序指令的执行次数（执行时间）。
空间复杂度（space complexity）：估算所需占用的存储空间。
1.3.1 时间复杂度
常见的时间复杂度从快到慢：
常数复杂度 O(1)
对数复杂度 O(logn)
线性时间复杂度 O(n)
线性对数复杂度 O(nlogn)
平方 O(
)
立方 O(
)
指数 O(
)
阶乘 O(n!)
1.3.2 空间复杂度
空间复杂度就是算法需要多少内存，占用了多少空间
常用的空间复杂度有O(1)、O(n)、O()
二、二分查找
二分查找算法也称折半查找，是一种非常高效的工作于有序数组的查找算法。
2.1 二分查找基础版
/**
* @description: 二分查找基础版
* @author: 憨憨浩浩
* @date: 2023/12/11 21:54
* @param: [a, target]
* @return: int
**/
public static int binarySearchBasic(int[] a, int target) {
// 定义左侧指针
int i = 0;
// 定义右侧指针
int j = a.length - 1;
// 当 i > j 时退出循环
while (i <= j){
// 定义中间指针
int m = (i + j) / 2;
if (a[m] > target){ // 目标值在左边
j = m - 1;
}else if (a[m] < target){ // 目标值在右边
i = m + 1;
}else { // 找到目标值返回对应索引
return m;
}
}
return -1; // 找不到目标值返回-1
}
(i + j) / 2 有没有问题?
有问题，当数组长度足够长是会发生问题；
@Test
public void Test01(){
int i = Integer.MAX_VALUE / 2;
int j = Integer.MAX_VALUE;
int m = (i + j) / 2;
System.out.println(m); // -536870913
}解决方案：
@Test
public void Test02(){
int i = Integer.MAX_VALUE / 2;
int j = Integer.MAX_VALUE;
int m = (i + j) >>> 2;
System.out.println(m); // 805306367
}2.2 二分查找改变版
另一种写法
/**
* @description: 二分查找改变版
* @author: 憨憨浩浩
* @date: 2023/12/11 22:10
* @param: [a, target]
* @return: int
**/
public static int binarySearchAlternative(int[] a,int target){
// 定义左侧指针
int i = 0;
// 定义右侧指针
int j = a.length;
// 当 i = j 时退出循环
while (i < j){
// 定义中间指针
int m = (i + j) /2;
if (a[m] > target){ // 目标值在左边
j = m;
} else if (a[m] < target) { // 目标值在右边
i = m + 1;
}else { // 找到目标值返回对应索引
return m;
}
}
return -1; // 找不到目标值返回-1
}
2.3 二分查找性能
2.4 二分查找平衡版
/**
* @description: 二分查找平衡版
* @author: 憨憨浩浩
* @date: 2023/12/13 13:46
* @param: [a, target]
* @return: int
**/
public static int binarySearchBalance(int[] a,int target){
// 定义左侧指针
int i = 0;
// 定义右侧指针
int j = a.length;
// 当 i + 1 > j 时退出循环
while (1 < j - i) {
// 定义中间指针
int m = (i + j) >>> 1;
if (target < a[m]) { // 目标值在左边
j = m;
} else {
i = m;
}
}
// 查到返回i，查不到返回-1
return (a[i] == target) ? i : -1;
}
2.5 二分查找 Java 版
Java8源码：
public static int binarySearch(int[] a, int key) {
return binarySearch0(a, 0, a.length, key);
}
private static int binarySearch0(int[] a, int fromIndex, int toIndex, int key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
2.6 Leftmost 与 Rightmost
/**
* @description: 二分查找返回左侧的索引值
* @author: 憨憨浩浩
* @date: 2023/12/15 20:21
* @param: [a, target]
* @return: int
**/
public static int binarySearchLeftmost1(int[] a,int target){
int i = 0, j = a.length - 1;
int candidate = -1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target < a[m]) {
j = m - 1;
} else if (a[m] < target) {
i = m + 1;
} else {
candidate = m; // 记录候选位置
j = m - 1; // 继续向左
}
}
return candidate;
}如果希望返回的是最右侧元素
/**
* @description: 二分查找返回最右侧值的索引
* @author: 憨憨浩浩
* @date: 2023/12/15 20:23
* @param: [a, target]
* @return: int
**/
public static int binarySearchRightmost1(int[] a,int target){
int i = 0, j = a.length - 1;
int candidate = -1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target < a[m]) {
j = m - 1;
} else if (a[m] < target) {
i = m + 1;
} else {
candidate = m; // 记录候选位置
i = m + 1; // 继续向右
}
}
return candidate;
}应用
对于 Leftmost 与 Rightmost，可以返回一个比 -1 更有用的值
Leftmost 改为
public static int binarySearchLeftmost(int[] a, int target) {
int i = 0, j = a.length - 1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target <= a[m]) {
j = m - 1;
} else {
i = m + 1;
}
}
return i;
}
Rightmost 改为
public static int binarySearchRightmost(int[] a, int target) {
int i = 0, j = a.length - 1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target < a[m]) {
j = m - 1;
} else {
i = m + 1;
}
}
return i - 1;
}大于等于中间值，都要向右找
几个名词
