二分搜索

1. 在二分查找技术中，我们在排序数组中通过递归地将区间分成两半来搜索元素。

2. 首先，我们将整个数组作为一个区间。

3. 如果主元（要搜索的项）小于区间中间的项，我们丢弃列表的后半部分，并通过计算新的中间和最后一个元素，递归地重复列表的前半部分的过程。

4. 如果主元（要搜索的项）大于区间中间的项，我们丢弃列表的前半部分，并通过计算新的开始和中间元素，递归地处理后半部分。

5. 重复检查，直到找到该值或区间为空。

分析

1. 输入：大小为 n 的数组 A，已按升序或降序排序。
2. 输出：分析以在大小为 n 的排序数组中搜索元素项。
3. 逻辑：设 T (n) = 在排序数组中将一个项目与 n 个元素进行比较的次数。

• 设置 BEG = 1 和 END = n
• 找到 mid =
• 将搜索项与中间项进行比较。

情况 1： item = A[mid]，则 LOC = mid，但它是最佳情况，T (n) = 1

情况 2： item ≠A [mid]，那么我们将数组分成两个大小相等的 。

再次找到半排序数组的中点并与搜索元素进行比较。

重复相同的过程，直到找到搜索元素。

T (n) = ...... (公式 1)

{将搜索元素与中间元素进行比较的时间，然后与数组的所选一半部分的一半进行比较}

至少会剩下一项，这就是为什么该项会比较出来，并且只完成一次比较，这就是为什么

是该等式的最后一项，它将等于 1