1、 查找算法介绍
在java中，我们常用的查找有四种:
1)顺序(线性)查找
2)二分查找/折半查找
3)插值查找
4)斐波那契查找
2 、线性查找算法
有一个数列：{1,8,10,89,1000,1234}，判断数列中是否包含此名称【顺序查找】要求:如果找到了，就提示找到，并给出下标值。
package com.petrel.search;
public class SeqSearch {
public static void main(String[] args) {
int arr[]={1,9,11,-1,34,89};
int value = seqSearch(arr,9);
if(value == -1){
System.out.println("没有找到值");
}else {
System.out.println("找到，下标为："+value);
}
}
private static int seqSearch(int[]arr,int value){
for (int i = 0;i< arr.length;i++){
if(arr[i] == value){
return i;
}
}
return -1;
}
}
结果是：
D:jdk1_8jdkinjava.exe "-javaagent:D:soft_installideaIntelliJ IDEA 2020.1.3libidea_rt.jar=13420:D:soft_installideaIntelliJ IDEA 2020.1.3in" -Dfile.encoding=UTF-8 -classpath D:jdk1_8jdkjrelibcharsets.jar;D:jdk1_8jdkjrelibdeploy.jar;D:jdk1_8jdkjrelibextaccess-bridge.jar;D:jdk1_8jdkjrelibextcldrdata.jar;D:jdk1_8jdkjrelibextdnsns.jar;D:jdk1_8jdkjrelibextjaccess.jar;D:jdk1_8jdkjrelibextjfxrt.jar;D:jdk1_8jdkjrelibextlocaledata.jar;D:jdk1_8jdkjrelibext
ashorn.jar;D:jdk1_8jdkjrelibextsunec.jar;D:jdk1_8jdkjrelibextsunjce_provider.jar;D:jdk1_8jdkjrelibextsunmscapi.jar;D:jdk1_8jdkjrelibextsunpkcs11.jar;D:jdk1_8jdkjrelibextzipfs.jar;D:jdk1_8jdkjrelibjavaws.jar;D:jdk1_8jdkjrelibjce.jar;D:jdk1_8jdkjrelibjfr.jar;D:jdk1_8jdkjrelibjfxswt.jar;D:jdk1_8jdkjrelibjsse.jar;D:jdk1_8jdkjrelibmanagement-agent.jar;D:jdk1_8jdkjrelibplugin.jar;D:jdk1_8jdkjrelib
esources.jar;D:jdk1_8jdkjrelib
t.jar;D: 2_my_codejavadataStructureoutproductiondataStructure com.petrel.search.SeqSearch
找到，下标为：1
Process finished with exit code 0
3、二分查找算法
1)二分查找：请对一个有序数组进行二分查找{1,8,10,89,1000,1234}，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示"没有这个数"。
2)二分查找算法的思路
3)二分查找的代码:
说明：增加了找到所有的满足条件的元素下标:课后思考题：{1,8,10,89,1000,1000，1234}当一个有序数组中，有多个相同的数值时，如何将所有的数值都查找到，比如这里的1000.
package com.petrel.BinarySearch;
import java.util.ArrayList;
import java.util.List;
public class BinarySearch {
public static void main(String[] args) {
int arr[] = { 1, 8, 10, 89,1000,1000, 1234 };
int index = binarySearch(arr,1000);
System.out.println("index:"+index);
int arr1[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 , 11, 12, 13,14,15,16,17,18,19,20 };
List<Integer> list = binarySearch2(arr,1000);
System.out.println("list:"+list);
}
private static int binarySearch(int[]arr,int findValue){
return binarySearch(arr,0,arr.length-1,findValue);
}
/**
* 二分查找算法
* @param arr 被查找数组
* @param left 左边的索引
* @param right 右边的索引
* @param findValue 需要查找的值
* @return 如果找到就返回下标，如果没有找到，就返回 -1
*/
private static int binarySearch(int[]arr,int left,int right,int findValue){
if(left > right){
return -1;
}
int mid = (left+right)/2;
int midValue =arr[mid];
if(findValue > midValue){
return binarySearch(arr,mid+1,right,findValue);
}else if(findValue < midValue){
return binarySearch(arr,left,mid-1,findValue);
}else {
return mid;
}
}
private static List<Integer> binarySearch2(int[]arr,int findValue){
return binarySearch2(arr,0,arr.length-1,findValue);
}
//完成一个课后思考题:
/*
* 课后思考题： {1,8, 10, 89, 1000, 1000，1234} 当一个有序数组中，
* 有多个相同的数值时，如何将所有的数值都查找到，比如这里的 1000
*
* 思路分析
* 1. 在找到mid 索引值，不要马上返回
* 2. 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
* 3. 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
* 4. 将Arraylist返回
*/
private static List<Integer> binarySearch2(int[]arr,int left,int right,int findValue){
if(left > right){
return new ArrayList<Integer>();
}
int mid = (left+right)/2;
int midValue = arr[mid];
if(findValue > midValue){
return binarySearch2(arr,mid+1,right,findValue);
}else if (findValue < midValue){
return binarySearch2(arr,left,mid-1,findValue);
}else {
// * 思路分析
// * 1. 在找到mid 索引值，不要马上返回
// * 2. 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
// * 3. 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
// * 4. 将Arraylist返回
List<Integer>resList = new ArrayList<Integer>();
int temp = mid-1;
while (true){
//向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
if(temp < 0 || arr[temp] !=findValue){
break;
}
//否则，就temp 放入到 resIndexlist
resList.add(temp);
//temp左移
temp-=1;
}
resList.add(mid);
//向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
temp = mid+1;
while (true){
if(temp > arr.length-1 || arr[temp] != findValue){
break;
}
//否则，就temp 放入到 resIndexlist
resList.add(temp);
temp+=1;
}
return resList;
}
}
}
结果是：
D:jdk1_8jdkinjava.exe "-javaagent:D:soft_installideaIntelliJ IDEA 2020.1.3libidea_rt.jar=1201:D:soft_installideaIntelliJ IDEA 2020.1.3in" -Dfile.encoding=UTF-8 -classpath D:jdk1_8jdkjrelibcharsets.jar;D:jdk1_8jdkjrelibdeploy.jar;D:jdk1_8jdkjrelibextaccess-bridge.jar;D:jdk1_8jdkjrelibextcldrdata.jar;D:jdk1_8jdkjrelibextdnsns.jar;D:jdk1_8jdkjrelibextjaccess.jar;D:jdk1_8jdkjrelibextjfxrt.jar;D:jdk1_8jdkjrelibextlocaledata.jar;D:jdk1_8jdkjrelibext
ashorn.jar;D:jdk1_8jdkjrelibextsunec.jar;D:jdk1_8jdkjrelibextsunjce_provider.jar;D:jdk1_8jdkjrelibextsunmscapi.jar;D:jdk1_8jdkjrelibextsunpkcs11.jar;D:jdk1_8jdkjrelibextzipfs.jar;D:jdk1_8jdkjrelibjavaws.jar;D:jdk1_8jdkjrelibjce.jar;D:jdk1_8jdkjrelibjfr.jar;D:jdk1_8jdkjrelibjfxswt.jar;D:jdk1_8jdkjrelibjsse.jar;D:jdk1_8jdkjrelibmanagement-agent.jar;D:jdk1_8jdkjrelibplugin.jar;D:jdk1_8jdkjrelib
esources.jar;D:jdk1_8jdkjrelib
t.jar;D: 2_my_codejavadataStructureoutproductiondataStructure com.petrel.BinarySearch.BinarySearch
index:5
list:[4, 5]
Process finished with exit code 0