《C#数据结构与算法》—二分查找法和顺序查找

6-1 二分查找和顺序查找、6-2 查找算法性能比较

---

顺序查找

功能解释：所有在 arr2 中出现但不在 arr1 中出现的元素。

• OrderSearch函数：在 arr 数组中线性查找 target，找到返回数组的索引i，未找到返回-1。
• 主函数：遍历 arr2 的每个元素，逐个检查是否存在于 arr1 中，并输出在 arr2 不在arr1中的元素。

二分查找法

什么是二分查找算法？

只能对有序排列进行高效查找（排序算法的作用）

查找23: 

TestSearch.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;namespace DataStucture
{class TestSearch{public static int BinarySearch(int[] arr,int target){int l = 0;int r = arr.Length - 1;while (l<=r){//int mid = (r+l)/2;//防止产生整形的溢出int mid = l + (r - l) / 2;if (target < arr[mid]){r = mid - 1;}else if (target > arr[mid]){l = mid + 1;}elsereturn mid;}return -1;}}
}

查找50：

查询算法复杂度分析 

顺序查找法：最坏的时间复杂度。也就是对于未命中查找的情况，需要遍历所有的元素查询。

二分查找法：最坏的时间复杂度。也就是对于未命中查找的情况。                                                                        每次比较都将数据规模缩小一半。

最坏情况（未命中查找）：

• 对于15个元素使用顺序查找最多进行了15次比较。
• 对于15个元素使用二分查找最多进行了 4 次比较。      log2 15 =4                                                  对于n个元素使用二分查找最多进行了log2n次比较。

顺序查找法	O(n)
二分查找法	O(log n)
O(1)<O(log n)<O(n)