二分查找详解

2024-02-06 05:07| 来源: 网络整理| 查看: 265

二分查找 1.什么是二分查找

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

2.二分查找的条件是一个有序数列必须是按照关键字大小进行排序 3.二分查找的实现原理

假设我们比较的有序数列有三个数,我们比较一个元素的值和数组中间位置的元素的值进行比较,如果比中间的元素大,则在有序数组的后半部分进行查找;如果中间位置的元素的值小,则跟有序数组的前半部分进行比较;如果相等,则找到了比较元素的位置.

3.1 流程把待查找的元素与有序数组的中间位置的值进行比较,如果大于则比较后半部分,小于则比较前半部分此后,有序数组变为原来数组的前半部分或者后半部分继续执行第一步,依次比较元素与当前数组的中间值的大小 3.2 代码实现 package binarySearch; /** * @author le */ public class BinarySearch { public static void main(String[] args) { // 有序的数组 int[] num = {1,7,9,44,56,100,121,199,233}; // 执行的次数 int count = 0; // 待查找的元素 int target = 44; // 数组的起始索引 int low = 0; // 数组中间元素的索引 int mid = 0; // 数组末尾的索引 int high = num.length - 1; // 判定条件 while(low // 待比较元素等于数组中间的值 count++; System.out.print("count: "+count+" 值: "+num[mid]); break; }else if(target // 待比较元素比数组中间元素的值大时 low = mid+1; count++; } } } }

主要是在于 low 和 high 还有 mid 的变化在每一次比较之后应该怎么变

3.3 图示

二分查找的流程

假设待查找的值为 44 有序查找数组为:arr[] = {1,7,9,44,56,100,121,199,233};

总计需要查找四次

第一次比较在这里插入图片描述