JavaSE基础50题:27(数组练习)二分查找
2023-12-29 06:09:41
概述
给定一个有序整数数组,实现二分查找。
二分查找的前提:必须是有序的数组!!
方法具体实现
如找数字5,定义L、R、M,其中M是L和R的中间位置,即(L+R) / 2 的位置。
如下图所示:
① L为0,R为4,此时M为2,2位置上的数字是3,3<5;
② 因为 3<5,所以,L=M+1的位置,R不变,此时M为 int (3+4)/2 = 3
,3位置的数字为4,4<5;
③因为 4<5,所以,L=M+1的位置,R不变,此时M为4,4位置上的数字为5,故找到数字5.
代码
public class P27 {
public static int func(int[] array,int num) {
int left = 0;
int rigth = array.length - 1;
while (left <= rigth){
//当left<=rigth时,进入循环,否则输出-1;
//即你想要找的数组找到最后没找到,说明这个数组中没有你要找的数字,输出-1作提示。
int mid = (left + rigth) / 2;
if (num > array[mid]){
left = mid + 1;
}else if (num < array[mid]) {
rigth = mid - 1;
}else {
return mid;
}
}
return -1;
}
public static void main(String[] args) {
int[] array = {11,22,33,44,55,66,77,88,99};
int a = func(array,99);
int b = func(array,2);
System.out.println(a);
System.out.println(b);
}
}
//输出结果
8
-1
如果数组是无序的,就需要用Arrays.sort()
方法先排个序,最终输出的位置是排完序后的位置。
public static void main(String[] args) {
int[] array2 = {2,5,6,3,8,4,1};
Arrays.sort(array2); //此时的顺序为{1,2,3,4,5,6,8}
System.out.println(func(array2, 1));
System.out.println(func(array2,5));
}
//输出结果
0
4
文章来源:https://blog.csdn.net/T2283380276/article/details/135279239
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!