java代码实现二分法查找
程序员文章站
2024-03-16 09:32:10
...
二分法查找的前提
该线性数组内的数字是有序的,如{1,2,3,4,5,6,7,8,9}等
二分法的实现
(1)首先,从数组的中间元素开始搜索,如果该元素正好是目标元素,则搜索过程结束,否则执行下一步。
(2)如果目标元素大于/小于中间元素,则在数组大于/小于中间元素的那一半区域查找,然后重复步骤(1)的操作。
package com.liao;
/**
* 二分法查找实现
*/
public class BinarySearch {
public static void main(String[] args) {
//1,目标数组
int[] arr = new int[]{1,2,3,4,5,6,7,8,9};
//2,要查找的目标元素
int target = 8;
//3,开始查找
int begin = 0;//用来记录开始位置
int end = arr.length-1;//用来记录结束位置
int mid = (begin+end)/2;//记录中间位置
int index = -1;//如果值为-1表示该数组没有该元素,如果有就把对应的下标值赋予它
while (true){
//1,判断中间的这个元素是不是要查找的元素
if(arr[mid]==target){
index = mid;
break;
}else {//2,中间元素不是目标元素
//判断中间元素与目标元素的大小
if(arr[mid]>target){//中间大于目标元素
end=mid-1;//把要结束的位置调到中间元素的前一个,缩小范围
}else {
//中间元素大于小于目标元素,把要开始的位置调到中间元素的后一个,缩小范围
begin=mid+1;
}
//3,重新计算中间位置,就这样反复计算,直到mid=target成立,跳出循环
mid = (begin+end)/2;
}
}
System.out.println("index = " + index);
}
}
下一篇: p7-11汽车加油问题