当前位置 博文首页 > 搜索算法_哈希表_Inmaturity_7的博客：数据结构和算法学习笔记三

最大化 缩小

    搜索算法_哈希表_Inmaturity_7的博客：数据结构和算法学习笔记三

    作者：[db:作者] 时间：2021-08-01 11:45

    数据结构和算法学习笔记三_搜索算法_哈希表

    一、查找算法

    1.二分查找

    单个搜索：找有序序列的中间值，

    相等：

    • 返回这个下标

    不相等：

    • 中间值小于查找的值，就搜索右半边
    • 中间值大于查找的值，就搜索左半边

    多个搜索：找有序序列的中间值，

    相等：

    • 将这个值加入集合，然后向左和向右其它相等的值(因为这个序列是有序的)

    不相等：

    • 中间值小于查找的值，就搜索右半边
    • 中间值大于查找的值，就搜索左半边
    1. 查找单个值（递归）
    package com.lxf.search;

import java.util.ArrayList;

public class BinarySearch {
    


    public static void main(String[] args) {
        int arr[]={1,8,10,89,1000,11111,1234};
        System.out.println(binarySearch(arr,0,arr.length-1,1000));
    }

    /**
     * @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;
        }
    }
}
    1. 查找单个值（非递归）
    package com.lxf.search;

public class BinarySearchNoRecur {
    public static void main(String[] args) {
        int[] arr = {1,3,5,7,9,18,19,22,100};
        int result = binarySearch(arr, 100);
        if(result>=0){
            System.out.println("查找到目标值的下标："+result);
        }else{
            System.out.println("未在数组查找到对应值");
        }
    }

    /**
     * 二分查找的非递归查找
     * @param arr  查找数组
     * @param target 目标值
     * @return
     */
    public static int binarySearch(int[] arr,int target){
        int left=0;
        int right=arr.length-1;
        while (left<=right){
            int mid=(left+right)/2;
            if(arr[mid]==target){
                return mid;//找到，返回对应值
            }else if(arr[mid]>target){
                right=mid-1;//继续向左查找
            }else{
                left=mid+1;//继续向右查找
            }
        }
        //未找到返回-1
        return -1;
    }
}
    1. 查找多个值
    package com.lxf.search;

import java.util.ArrayList;
import java.util.List;

public class BinarySearch {
    private static List<Integer> list=new ArrayList<>();


    public static void main(String[] args) {
        int arr[]={1,8,10,89,1000,1000,1234};
        binarySearch(arr,0,arr.length-1,1000);
        for (Integer integer : list) {
            System.out.print(integer+" ");
        }
    }

    /**
     * @param arr 数组
     * @param left 左边的索引
     * @param right 右边的索引
     * @param findVal 要查找的值
     * @return 如果找到直接返回下标，如果没找到返回-1
     */
    //二分查找算法
    public static void binarySearch(int[] arr,int left,int right,int findVal){
        //中止条件
        if(left>right){
            return;
        }
        int mid=(left+right)/2;
        int midVal=arr[mid];

        if(findVal>midVal){
            //向右递归
             binarySearch(arr,mid+1,right,findVal);
        }else if(findVal<midVal){
            //向左递归
             binarySearch(arr,left,mid-1,findVal);
        }else{
            list.add(mid);
            int i=mid+1;
            int j=mid-1;
            while(i<=right){
                if(arr[i]==findVal){
                    list.add(i);
                }
                i++;
            }
            while(j>=left){
                if(arr[j]==findVal){
                    list.add(j);
                }
                j--;
            }
        }
    }
}

    2.插值查找

    1. 插值查找原理介绍:

    插值查找算法类似于二分查找，不同的是插值查找每次从自适应 mid 处开始查找。

    1. 将折半查找中的求 mid 索引的公式 , low 表示左边索引 left, high 表示右边索引 right.

    key 就是前面我们讲的 findVal

    **二分：**mid=(low+high)/2=low+(high-low)/2

    =>

    **插值：**mid=low+((key-a[low])/a[high]-a[low])*(high-low)

    1. int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]) ;//插值索引

    对应前面的代码公式：

    int mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left])

    1. 单个查找
    package com.lxf.search;

public class InsertValueSearch {
        public static void main(String[] args) {
            int arr[]={1,8,10,89,1000,11111,1234};
            System.out.println(insertValue(arr,0,arr.length-1,1000));
        }

    public static int insertValue(int[] arr,int left,int right,int findVal){
        if(left>right||findVal<arr[0]||findVal>arr[arr.length-1]){
            return -1;
        }
    //求出mid
    int mid=left+(right-left)*(findVal-arr[left])/(arr[right]-arr[left]);
        int midVal=arr[mid];
        if(findVal>midVal){
            //向右查找
            return insertValue(arr, mid+1, right, findVal);
    上一篇：Inmaturity_7的博客：算法练习帖--27--变位词组(Java)
    下一篇：没有了