Qz学算法-数据结构篇(查找算法--线性、二分)

时间：2022-03-21 00:57:21

查找算法

介绍

在Java中,常用的查找算法有四种

1)顺序(线性)查找

2)二分查找/折半查找

3)插值查找

4)斐波那契查找

1.线性查找算法

1.需求引入

有一个数列：{1,8,10,89,1000，1234},判断数列中是否包含此名称 【顺序查找】要求：如果找到了，就提示找到，并给出下标值。

2.代码实现

public class SeqSearch {
public static void main(String[] args) {
int arr[] = {1, 9, 113, 2, -23, 124, 346, 63};//没有顺序的数组
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 (arr[i] == value) {
return i;
            }
        }
return -1;
    }
}

线性查找很简单很简单,循环遍历数组,if判断,找到了就拿到下标,没找到就返回-1

2.二分查找(必须掌握)

1.需求引入

请对一个有序数组进行二分查找{1,8,10,89,1000,1234}，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示”没有这个数”。

2.思路分析

  1. 首先确定该数组的中间的下标 mid =(left+right)/2
  2. 然后让需要查找的数findVal和arr[mid]比较
  1. findVal>arr[mid],说明你要查找的数在mid的右边，因此需要递归的向右查找
  2. findVal<arr[mid],说明你要查找的数在mid的左边，因此需要递归的向左查找
  3. findVal=arr[mid]说明找到，就返回
  1. 结束递归的条件
  1. 找到就结束递归
  2. 递归完整个数组，仍然没有找到findVal,也需要结束递归当Ieft>right就需要退出

3.代码实现(案例一)

package search;

/**
* @author LeeZhi
* @version 1.0
*/
//注意:使用二分查找的前提是 该数组有序
public class BinarySearch {
public static void main(String[] args) {
int[] arr = {1, 8, 10, 89, 1000, 1024};
int resIndex = binarySearch(arr,0,arr.length,10);
System.out.println("resIndex"+resIndex);
    }

/**
*
* @param arr 数组
* @param left 右边的索引
* @param right 左边的索引
* @param findVal 要查找的值
* @return 如果找到就返回下标,如果没有找到就返回一个-1
*/
public static int binarySearch(int[] arr, int left, int right , int findVal) {
//当left>right时，说明递归整个数组，但是没有找到
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;
        }
    }
}

4.代码实现(案例二)

如果这个集合是这个样子int[] arr = {1, 8, 10, 89, 1000, 1000, 1024, 1024},上面的二分查找只会返回第一个出现的重复的数字,我们案例二想要实现的就是,在集合里右重复的数字,我们把他都查出来

思路分析

  1. 在找到mid索引值，不要马上返回
  2. 向mid素引值的左边扫描，将所有满足1000，的元素的下标，加入到集合ArrayList
  3. 向mid索引值的右边扫描，将所有满足I000,的元素的下标，加入到集合ArrayList
  4. 将Arraylist返回
public static ArrayList<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {
//当left>right时，说明递归整个数组，但是没有找到
if (left > right) {
return new ArrayList<Integer>();
    }

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 {
ArrayList<Integer> resIndexList = new ArrayList<>();
//在找到mid索引值，不要马上返回 向mid素引值的左边扫描，将所有满足1000，的元素的下标，加入到集合ArrayList
int temp= mid -1;
while(true){
if (temp<0||arr[temp]!=findVal){//退出
break;
            }
//否则,就temp放入到resIndexList
resIndexList.add(temp);
temp-=1;
        }
resIndexList.add(mid);
//向mid索引值的右边扫描，将所有满足I000,的元素的下标，加入到集合ArrayList
temp = mid +1;
while(true){
if (temp > arr.length-1||arr[temp]!=findVal){ //退出
break;
            }
//否则,就temp放入到resIndexList
resIndexList.add(temp);
temp+=1; //temp右移
        }
//将Arraylist返回
return resIndexList;
    }
}
标签：

相关文章