标签：java target int 数组 二分法 middle 查找 arr1
一、线性查找
思想：如果想在一个数组中查找是否有某个元素，最容易想到的办法就是遍历数组，将数组中元素与想要查找的元素逐个对比，如果相等表示找到了，如果不等，则表示没找到。这就是线性查找的思想。
| 案例说明 | 定义数组：int[] arr1 = new int[]{34,54,3,2,65,7,34,5,76,34,67};
查找元素5是否在上述数组中出现过？如果出现，输出对应的索引值。 |
| 代码实现 | public class LinearSearchTest {
public static void main(String[] args) { int[] arr1 = new int[]{34,54,3,2,65,7,34,5,76,34,67}; int target = 5;
// target = 15; //查找方式：线性查找
//方式1：
// boolean isFlag = true;
// for(int i = 0;i < arr1.length;i++){
// if(target == arr1[i]){
// System.out.println("找到了" + target + ",对应的位置为：" + i);
// isFlag = false;
// break;
// }
// }
//
// if(isFlag){
// System.out.println("不好意思，没有找到此元素");
// } //方式2：
int i = 0;
for(;i < arr1.length;i++){
if(target == arr1[i]){
System.out.println("找到了" + target + ",对应的位置为：" + i);
break;
} } if(i == arr1.length){
System.out.println("不好意思，没有找到此元素");
}
}
} |
二、二分法查找
a）二分法查找的前提条件：数组元素有序排列。
b）实现步骤图示
| 案例说明 | 案例2：二分法查找 定义数组：int[] arr2 = new int[]{2,4,5,8,12,15,19,26,37,49,51,66,89,100};
查找元素5是否在上述数组中出现过？如果出现，输出对应的索引值。 |
| public class BinarySearchTest {
public static void main(String[] args) { int[] arr2 = new int[]{2,4,5,8,12,15,19,26,37,49,51,66,89,100}; int target = 5;
// target = 17; int head = 0;//默认的首索引
int end = arr2.length - 1;//默认的尾索引
boolean isFlag = false;//判断是否找到了指定元素
while(head <= end){ int middle = (head + end) / 2; if(target == arr2[middle]){
System.out.println("找到了" + target + ",对应的位置为：" + middle);
isFlag = true;
break;
}else if(target > arr2[middle]){
head = middle + 1;
}else{//target < arr2[middle]
end = middle - 1;
}
} if(!isFlag){
System.out.println("不好意思，未找到");
}
}
} |
三、小结
顺序查找：
> 优点：算法简单；
> 缺点：执行效率低。执行的时间复杂度O(N)
二分法查找：
> 优点：执行效率高。执行的时间复杂度O(logN)
> 缺点：算法相较于顺序查找难一点；前提：数组必须有序
标签：java,
target,
int,
数组,
二分法,
middle,
查找,
arr1
From： https://blog.csdn.net/weixin_44554794/article/details/140335592