11ss
1.线性查找
代码实现:
public class SeqSearch {
public static void main(String[] args) {
int arr[]={1,9,11,-1,34,89};//没有顺序的数组
int index = seqSearch(arr, 11);
if (index==-1){
System.out.println("没有找到");
}else {
System.out.println("找到了,下标为" + index);
}
}
public static int seqSearch(int[] arr,int value){
for (int i = 0; i < arr.length; i++) {
if (value==arr[i]){
return i;
}
}
return -1;
}
}
2.二分查找
请对一个有序数组进行二分查找 {1,8, 10, 89, 1000, 1234} ,输入一个数看看该数组是否存在此数,并且求出下标,如果没有就提示"没有这个数"。
代码实现:
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,1000,1000,1234};
// int index = binarySearch(arr, 0, arr.length - 1, 9);
// System.out.println(index);
List<Integer> indexList = binarySearch2(arr, 0, arr.length - 1, 1000);
System.out.println(indexList);
}
//二分查找
/**
*
* @param arr 数组
* @param left 左边的索引
* @param right 右边的索引
* @param findVal 要查找的值
* @return 如果找到就返回下标,如果没有找到,就返回-1
*/
public static int binarySearch(int[] arr,int left,int right,int findVal){
//说明递归完整个数组,但没有找到
if (left>right){
return -1;
}
int mid=(left+right)/2;
int midVal=arr[mid];
if (findVal>midVal){//向右递归
return binarySearch(arr,mid+1,right,findVal);
}else if (findVal<midVal){//向左递归
return binarySearch(arr,left,mid-1,findVal);
}else {
return mid;
}
}
/*
有多个相同的数值时,如何将所有的数值都查找到,比如这里的1000
思路分析
1.在找到mid索引值,不要马上返回
2.向mid索引值的左边扫描,将所有满足1000,的元素的下标,加入到集合ArrayList
3.向mid索引值的右边扫描,将所有满足1000,的元素的下标,加入到集合ArrayList
4.将Arraylist返回
*/
public static List<Integer> binarySearch2(int arr[],int left,int right,int findVal){
//说明递归完整个数组,但没有找到
if (left>right){
return new ArrayList<>();
}
int mid=(left+right)/2;
int midVal=arr[mid];
if (findVal>midVal){//向右递归
return binarySearch2(arr,mid+1,right,findVal);
}else if (findVal<midVal){//向左递归
return binarySearch2(arr,left,mid-1,findVal);
}else {
List<Integer> list=new ArrayList<>();
int temp=mid-1;
while (temp>=0&&arr[temp]==findVal){
list.add(temp);
temp--;
}
list.add(mid);
temp=mid+1;
while (temp<=arr.length&&arr[temp]==findVal){
list.add(temp);
temp++;
}
return list;
}
}
}
3.插值查找
插值查找注意事项:
1)对于数据量较大,关键字分布比较均匀的查找表来说,采用插值查找,速度较快.
2)关键字分布不均匀的情况下,该方法不一定比折半查找要好
代码实现:
public class InsertValueSearch {
public static void main(String[] args) {
int[] arr=new int[100];
for (int i = 0; i < 100; i++) {
arr[i]=i+1;
}
int index = insertValueSearch(arr, 0, arr.length - 1, 100);
System.out.println(index);
}
//递归
public static int insertValueSearch(int[] arr,int left,int right,int findVal){
//注意:findVal<arr[0]和findVal>arr[arr.length-1]必须需要
if (left>right||findVal<arr[0]||findVal>arr[arr.length-1]){
return -1;
}
int mid=left+(right-left)*(findVal-arr[left])/(arr[right]-arr[left]);
int midVal=arr[mid];
if (findVal>midVal){//向右递归
return insertValueSearch(arr,mid+1,right,findVal);
}else if (findVal<midVal){//向左递归
return insertValueSearch(arr,left,mid-1,findVal);
}else {
return mid;
}
}
}