时间:2021-05-20
这篇文章主要介绍了Java二分查找算法实现代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
二分查找:
两种方式:非递归方式和递归方式
主要思路:对于已排序的数组(先假定是从小到大排序), 先定义两个"指针", 一个"指向"首元素low, 一个"指向"末尾元素high. 然后, 开始折半比较, 即让要查找的数与数组中间的元素(索引为 low+high/2)比较. 若要查找的数比中间数小, 说明要查找的数在数组左侧(注意前提是数组从小到大排序), 否则说明该数在数组的右侧. 如果low最后还比high大,俩"指针"交叉了, 说明没有找到该数, 即数组不存在该数.
注意事项:排序规则与数组的排序顺序有关, 即从大到小排序和从小到大排序是不一样的!!!
代码如下
class BinarySearch { // 二分查找非递归方式 // arr 给定已排序数组 // num 要查找的数 public static int search(int[] arr, int num) { int low = 0; int high = arr.length - 1; int mid = 0; while (low <= high) { mid = (low + high) / 2; if (num < arr[mid]) { high = mid - 1; } if (num > arr[mid]) { low = mid + 1; } if (num == arr[mid]) { return mid; } } return -1; // 没找到 } // 二分查找递归方式 // arr 给定已排序数组 // num 要查找的数 // low 初始左侧指针 指向第一个元素 // high 初始末尾指针 指向最后一个元素 public static int binarySearch(int[] arr, int num, int low, int high) { int mid = (low + high) / 2; // 递归结束条件 if (low > high) { return -1; } if (num < arr[mid]) { return binarySearch(arr, num, low, mid - 1); } else if (num == arr[mid]) { return mid; } else { return binarySearch(arr, num, mid + 1, high); } } public static void main(String[] args) { // 给定数组 从小到大排序. int[] arr = {2, 3, 5, 7, 8, 9, 11, 12, 15}; // int[] arr = {15, 12, 11, 9, 8, 7, 5, 3, 2}; int m = 3; // int index = search(arr, m); int index = binarySearch(arr, m, 0, arr.length - 1); System.out.println(index); } }以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文实例讲述了C语言二分排序与查找算法。分享给大家供大家参考,具体如下:题目:首先产生随机数,再进行快速排序,再进行二分查找。实现代码:#include#inc
本文实例讲述了Java实现二分查找算法。分享给大家供大家参考。具体如下:1.前提:二分查找的前提是需要查找的数组必须是已排序的,我们这里的实现默认为升序2.原理
java算法二分查找与折半查找折半查找:首先数组是已经排好序的实例代码:packagecom.hao.myrxjava;/***折半查找:首先数组是已经排好序的
本文实例为大家分享了Java实现二分查找的变种,供大家参考,具体内容如下普通二分查找:先回顾一下普通的二分查找注意:二分查找有这样一个问题:当数组中数有重复时,
本文实例为大家分享了java实现二分法查找出数组重复数字的具体代码,供大家参考,具体内容如下packageoffer;/***二分查找的思想来找到数组中重复的数