二分查找算法
2021/11/3 1:10:00
本文主要是介绍二分查找算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
二分查找算法
前提:有序数组
- 首先确定整个查找区间的中间位置 mid = strat+(end-strat)/2
- 用待查关键字key值与中间位置的关键字值进行比较;
- 若相等,则查找成功
- 若大于,则在后(右)半个区域继续进行折半查找
- 若小于,则在前(左)半个区域继续进行折半查找
- 重复上述步骤。
方式一:非递归
public static int search(int key, int[] arr) { int start = 0; int end = arr.length - 1; while (start <= end) { int mid = start + (end - start) / 2; if (key< arr[mid]) { end = mid - 1; } else if (key > arr[mid]) { start = mid + 1; } else { return mid; } } return -1; }
测试
public static void main(String[] args) throws InterruptedException { int[] a={1,2,3,6,7,9,12,23,45}; System.out.println(DataTest.search(3,a));//输出2 }
方式二:递归
public static int search2(int key, int[] arr, int start, int end) { if (start > end) { return -1; } int mid = start + (end - start) / 2; if (key < arr[mid]) { return search2(key, arr, start, mid - 1); } else if (key > arr[mid]) { return search2(key, arr, mid + 1, end); } else { return mid; } }
测试
public static void main(String[] args) throws InterruptedException { int[] a = {1, 2, 3, 6, 7, 9, 12, 23, 45}; System.out.println(DataTest.search2(3, a,0,a.length-1));//输出2 }
為什麼start=mid + 1,為什麼end=mid - 1:因为每一次查找都要去掉中间值。举例{1, 2, 3, 4, 5, 6, 7, 8, 9,10}第一次二分mid (下标)为4,排除掉元素5,如果查找的数在上半段{1, 2, 3, 4},start=0;end=4-1=3;下半段{6, 7, 8, 9,10} start=4+1=5;end=9
这篇关于二分查找算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南