二分查找算法和BinarySearch

思想

二分查找 又被称为折半查找 ，是一种具有较高执行效率的检索方式。
该方法充分运用了元素之间的有序特性，通过采用分治策略 ，能够在最坏情况下以O(log n)的时间复杂度完成搜索操作。其核心原理为：（此处假设数组中的元素按照升序进行排列）将包含n个元素的数组划分为数量相近的两个部分，选取a[n/2]与目标值x进行对比，若x等于a[n/2]，则表示成功找到x，此时算法结束。若x小于a[n/2]，则只需在数组a的左半区域继续寻找x；若x大于a[n/2]，则只需在数组a的右半区域继续寻找x。

要求

• 数据组织形式需采用线性结构 。
  • 结构中的各个组成单元须依据特定的数值规则进行顺序排布 。

复杂度

时间复杂度分析

时间复杂度本质上取决于while循环执行的次数，整个过程包含n个元素，随着循环逐步推进，剩余待处理元素的数量依次为n、n/2、n/4、…、n/2^k（其中k代表循环的次数）。
考虑到在取整之后，n/2^k的值仍然大于等于1，
因此设定n/2^k=1，
由此可得k等于以2为底的n的对数，即k=log₂n。
综上所述，该算法的时间复杂度可表示为O(h)=O(log₂n)。

代码实现

核心类别：

    public class B