写点什么

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

作者:浅辄
  • 2023-04-25
    吉林
  • 本文字数:2139 字

    阅读完需:约 7 分钟

查找算法

介绍

在 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. 结束递归的条件

  2. 找到就结束递归

  3. 递归完整个数组,仍然没有找到 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; }}
复制代码


发布于: 刚刚阅读数: 4
用户头像

浅辄

关注

大丈夫生于天地之间,岂能郁郁久居人之下 2022-11-08 加入

Java、Spider、Go

评论

发布
暂无评论
Qz学算法-数据结构篇(查找算法--线性、二分)_数据结构_浅辄_InfoQ写作社区