数据结构和算法 - 二分查找

数据结构和算法二进制搜索 - 使用c，C ++和Java学习数据结构和算法，从简单和简单的步骤开始，从基本到高级概念，包括概述，环境设置，算法，渐近分析，贪婪算法，分而治之，动态编程，数据结构，数组，链接列表，双链表，循环列表，堆栈，解析表达式，队列，优先级队列，线性，二进制，插值搜索，树，树遍历，二进制搜索树，B +，AVL，跨越，塔河内，哈希表，堆，图，深度，广度优先遍历，搜索技术，排序技术，排序算法，泡沫，合并排序算法，插入，选择，壳，快速排序，递归，斐波那契系列。

二进制搜索是一种快速搜索算法，运行时复杂度为O(log n).这种搜索算法的工作原则是分而治之.为使此算法正常工作，数据收集应采用排序形式.

二进制搜索通过比较集合的最中间项来查找特定项.如果匹配发生，则返回项目的索引.如果中间项大于项，则在中间项左侧的子阵列中搜索项.否则，在中间项右侧的子阵列中搜索项.此过程在子数组上继续，直到子数组的大小减小到零.

二进制搜索的工作原理？

对于二进制搜索工作，必须对目标数组进行排序.我们将用一个图例来学习二元搜索的过程.以下是我们的排序数组，让我们假设我们需要使用二进制搜索来搜索值31的位置.

二进制搜索

首先，我们将使用此公式确定数组的一半 :

  mid = low +  (高 - 低)/2

这里是，0 + (9 - 0)/2 = 4(整数值为4.5).所以，4是数组的中间.

二进制搜索

现在我们将位置4存储的值与搜索的值进行比较，即31.我们发现位置4的值是27，这不匹配.由于值大于27并且我们有一个排序数组，所以我们也知道目标值必须位于数组的上半部分.

二进制搜索

我们将低音改为中音 + 1并再次找到新的中间值.

  low = mid + 1  mid = low + (high - low)/2

我们新的中期现在是7.我们将位置7存储的值与目标值31进行比较.

二进制搜索

存储在位置7的值不匹配，而是比我们正在寻找的值更多.因此，该值必须位于此位置的下半部分.

二进制搜索

因此，我们再次计算中间值.这次是5.

二进制搜索

我们比较值使用我们的目标值存储在位置5.我们发现它是一个匹配.

二进制搜索

我们得出结论目标值31存储在位置5.

二进制搜索将可搜索项目减半，从而减少了对比数非常少的比较次数.

伪代码

二进制搜索算法的伪代码应如下所示;

Procedure binary_search   A ← sorted array   n ← size of array   x ← value to be searched   Set lowerBound = 1   Set upperBound = n    while x not found      if upperBound < lowerBound          EXIT: x does not exists.         set midPoint = lowerBound + ( upperBound - lowerBound ) / 2            if A[midPoint] < x         set lowerBound = midPoint + 1               if A[midPoint] > x         set upperBound = midPoint - 1       if A[midPoint] = x          EXIT: x found at location midPoint   end while   end procedure

要了解使用C编程语言中的数组的二进制搜索实现.