TODO待更新

查找算法

(1)二分查找(Binary Search)✔

时间复杂度:O(log n)
空间复杂度:O(1)

代码片段

public int BinarySearch(int target) 
{
int left = 1;
int right = 1000;
while (left <= right)
{
int mid = (left + right) / 2;
int val = mid;
if (val > target)
{
right = mid - 1;
}
else if (val < target)
{
left = mid + 1;
} else
{
return mid;
}
}
return left;
}

核心思想

  1. 在一个有序的数据集合中快速定位目标值,通过每次排除一半的数据范围来逐步缩小查找范围,最终找到目标值或确定目标值不存在于数据集合中
  2. 分治,即将一个大问题分割成两个或多个小问题,在较小的范围内快速解决问题。

具体应用

比如你想在一个有序的从小到大排列的数组中搜索目标值。

  1. 初始时,可以将搜索范围设置为整个数组,然后取中间位置的值。
  2. 如果中间位置的值等于目标值,则直接返回结果;
  3. 如果中间位置的值大于目标值,则说明目标值可能在左半部分,需要在左半部分继续搜索;
  4. 如果中间位置的值小于目标值,则说明目标值可能在右半部分,需要在右半部分继续搜索。
    如此反复进行,每次可以通过减少一半的搜索范围来快速逼近目标值,最终可以得到目标值或判断目标值不存在于数组中。

(2)线性查找(Linear Search)✔

时间复杂度:O(n)
空间复杂度:O(1)

代码片段

public int LinearSearch(int target) 
{
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] == target)
{
return i;
}
}
return -1;
}

核心思想

  1. 直接从头到尾遍历数组,简单粗暴,也是最经典最常用的一个

(3)插值查找(Interpolation Search)

代码片段

public int InterpolationSearch(int[] arr, int target)
{
int low = 0;
int high = arr.Length - 1;
while (low <= high && target >= arr[low] && target <= arr[high])
{
int pos = low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low]);
if (arr[pos] == target)
{
return pos;
}
else if (arr[pos] < target)
{
low = pos + 1;
}
else
{
high = pos - 1;
}
}
return -1;
}

核心思想

  1. xxxxxxxx
  2. xxxxxxxx

具体应用

  1. xxxxxxxx
  2. xxxxxxxx

(4)斐波那契查找(Fibonacci Search)

代码片段


(5)树表查找(Tree Search)

代码片段


(6)哈希查找(Hash Search)

代码片段


(6)递归查找(Recursive Search)

代码片段


贪心算法

动态规划算法

图算法