Java二分查找算法实现代码实例

Java二分查找算法实现代码实例

这篇文章主要介绍了java二分查找算法实现代码实例,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下

二分查找:

两种方式: 非递归方式和递归方式

主要思路: 对于已排序的数组(先假定是从小到大排序), 先定义两个"指针", 一个"指向"首元素low, 一个"指向"末尾元素high. 然后, 开始折半比较, 即让要查找的数与数组中间的元素(索引为 low+high/2)比较. 若要查找的数比中间数小, 说明要查找的数在数组左侧(注意前提是数组从小到大排序), 否则说明该数在数组的右侧. 如果low最后还比high大,俩"指针"交叉了, 说明没有找到该数, 即数组不存在该数.

注意事项: 排序规则与数组的排序顺序有关, 即从大到小排序和从小到大排序是不一样的!!!

代码如下

class BinarySearch {

// 二分查找非递归方式

// arr 给定已排序数组

// num 要查找的数

public static ihttp://nt 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 = midhttp:// + 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);

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。