Java二分查找_图文 Java 二分查找_图文

一、二分查找概念

二分查找又被称为折半查找，其适用于已按升序或降序排列的数据集合中寻找特定元素，该方法属于一种查找效率相对较高的技术手段。

二、二分查找原理

1.二分查找算法所应用的数组必须为已按数值顺序排列的结构。

2.在查找过程中，需要将待寻找的目标值与当前搜索区间内的中间位置元素进行比对。若两者相等，则完成查找任务；若不相等，则根据比较结果将目标值限定在较大的或较小的区间内继续执行比对操作。

3.借助分组策略，可使每次搜索的范围缩减至原先的一半。

4.不断重复第二步的操作流程，直至目标元素与当前搜索区间中位数相匹配，或确认该元素不存在于数组中为止，此时查找过程终止。

5.二分查找算法的时间复杂度为O(log2n)。

三、二分查找的具体步骤

【给定一个包含n个元素的有序数组A，其中满足A0<=A1<=A2<=·······<=An-1，同时设定一个待查找的目标值target，

若存在该值则返回其对应的索引位置

若不存在该值则返回索引-1

1、初始化i=0，j=n-1

2、当i>j时，终止查找过程，判定未找到目标值，返回-1

3、确定中间索引m，计算方式为m=floor((i+j)/2)，其中floor表示向下