1. 顺序(线性)查找

思路:从头元素开始逐一开始与被查找元素比较 - 相等则返回,不想等则继续下一个元素,直至遍历完整个容器

public class SequentialSearch {
   
     

    public static int search(int[] arrs, int value) {
   
     

        for(int index = 0; index < arrs.length; index++) {
   
     
            if(arrs[index] == value) {
   
     
                return index;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
   
     

        int[] arrs = {
   
     1,-5,20,30,60};
        int value = -20;

        int index = search(arrs, value);

        if(index != -1) {
   
     
            System.out.println("查找到数值" + value + "在数组中的下标是" + index);
        }else {
   
     
            System.out.println("没有查找到");
        }
    }

}

2. 二分(折半)查找 - 有序的元素组

nlog 2

思路

  1. 先找中间元素下标 - midIndex = (left+right)/2
  2. 比较查找的元素searchValue与中间元素sortedArr[midIndex]
    2.1 如果 searchValue > sortedArr[midIndex] - 向右半部分递归查找
    2.2 如果 searchValue < sortedArr[midIndex] - 向左半部分递归查找
    2.3 如果 searchValue = sortedArr[midIndex] - 返回midIndex

递归结束条件 - 满足任意一个即可

1、 left>right;

2、 searchValue=sortedArr[midIndex];

 

2.1 递归

public class BinarySearch {
   
     

    //快速排序 - 递归
    public static void quickSort(int[] array, int startIndex, int endIndex) {
   
     
        if (startIndex >= endIndex)
            return;
        int left = startIndex;
        int right = endIndex;
        int temp = array[startIndex];
        while (left < right) {
   
     
            while (left < right && array[right] >= temp) right--;
            array[left] = array[right];
            array[right] = temp;
            while (left < right && array[left] <= temp) left++;
            array[right] = array[left];
            array[left] = temp;
        }
        quickSort(array, startIndex, left - 1);
        quickSort(array, left + 1, endIndex);
    }

    public static int[] sort(int[] arrs) {
   
     
        int[] copyArr = arrs.clone();
        quickSort(copyArr, 0, arrs.length - 1);
        return copyArr;
    }

    //二分查找
    public static int search(int[] arrs, int left, int right, int searchValue) {
   
     

        //找不到直接返回-1
        if (left > right) {
   
     
            return -1;
        } else {
   
     
            int midIndex = (left + right) / 2;

            if (searchValue > arrs[midIndex]) {
   
     
                return search(arrs, midIndex + 1, right, searchValue);
            } else if (searchValue < arrs[midIndex]) {
   
     
                return search(arrs, left, midIndex - 1, searchValue);
            } else {
   
     
                return midIndex;
            }
        }
    }

    //查询查找元素的所有索引
    public static Integer[] searchAllIndex(int[] arrs, int searchValue) {
   
     
        int index = search(arrs, 0, arrs.length - 1, searchValue);

        List<Integer> indexs = new ArrayList<>(arrs.length);
        indexs.add(index);

        if(index != -1) {
   
     
            int currentIndex = index;
            //往左寻找
            while (true) {
   
     
                currentIndex = currentIndex - 1;
                if (currentIndex < 0)
                    break;
                if (arrs[currentIndex] == searchValue) {
   
     
                    indexs.add(currentIndex);
                } else {
   
     
                    break;
                }
            }

            //往右寻找
            currentIndex = index;
            while (true) {
   
     
                currentIndex = currentIndex + 1;
                if (currentIndex == arrs.length)
                    break;
                if (arrs[currentIndex] == searchValue) {
   
     
                    indexs.add(currentIndex);
                } else {
   
     
                    break;
                }
            }

        }
        Integer[] indexss = new Integer[indexs.size()];
        return indexs.toArray(indexss);

    }

    public static void main(String[] args) {
   
     
        int[] a = {
   
     4, 5, 10, 3, 1, 5, 7, 9};
        int searchValue = 9;
        int[] sortedArrs = sort(a);

        int index = search(sortedArrs, 0, sortedArrs.length - 1, searchValue);
        System.out.printf("未排序数组:%s\n", Arrays.toString(a));
        System.out.printf("排序后数组:%s\n", Arrays.toString(sortedArrs));
        if (index != -1) {
   
     
            System.out.printf("查找的元素%d在排序数组中第%d位置\n", searchValue, index);
        } else {
   
     
            System.out.println("查找不到");
        }

        System.out.printf("查找的元素5在排序数组中所有位置是%s\n",Arrays.toString(searchAllIndex(sortedArrs,5)));

    }

}

 

2.2 非递归 - 循环

//二分查找 - 非递归
public static int search(int[] arrs, int searchValue) {
   
     

    int left = 0;
    int right = arrs.length;

    while(true) {
   
     

        if (left > right) {
   
     
            return -1;
        }else {
   
     
            Integer mid = (left + right)/2;

            if(arrs[mid] == searchValue) {
   
     
                return mid;
            }

            if(arrs[mid] > searchValue) {
   
     
                right = mid - 1;
            }else {
   
     
                left = mid + 1;
            }
        }

    }
}

3. 插值查找 - 有序的元素组

思路:跟二分查找差不多,只是中间索引公式不一样而已

中间索引有searchValue参与,自适应

使用场景

有序数组元素间差值分布比较一样 - 类似线性方程值

元素间分布不均匀不一定比二分查找快

二分查找中间索引公式: ( left + right )/2 →  left + 1/2( right - left )

//其实就是上面公式的变种
插值查找中间索引公式: left +  ( searchValue - arr[left] )/( arr[right]-arr[left] ) * ( right-left )

public class InsertSearch {
   
     
    public static Integer[] search(int[] arrs, int left, int right, int searchValue) {
   
     

        List<Integer> indexs = new ArrayList<Integer>(arrs.length);
        
        //特点注意后面两个判断条件一定要加,- 
        // 因为midIndex有searchValue进行参与计算,一旦searchValue非常大时,一定会超出索引
        // 当然你也可以在计算midIndex后进行判断是否超出数组范围。超过则返回-1 - 一样的效果
        if(left > right || searchValue >  arrs[arrs.length-1] || searchValue <  arrs[0]) {
   
     
            indexs.add(-1);
        }else {
   
     
            int midIndex = left +  ( searchValue - arrs[left] )/( arrs[right]-arrs[left] ) * ( right-left );

            if(searchValue > arrs[midIndex]) {
   
     
                return search(arrs,midIndex+1, right, searchValue);
            }else if(searchValue < arrs[midIndex]) {
   
     
                return search(arrs,left, midIndex+1, searchValue);
            }else {
   
     
                indexs.add(midIndex);

                //往左扫描
                int curIndex = midIndex;
                while(true) {
   
     
                    curIndex = curIndex - 1;
                    if(curIndex < 0) {
   
     
                        break;
                    }else {
   
     
                        if(arrs[curIndex] == searchValue) {
   
     
                            indexs.add(curIndex);
                            continue;
                        }
                        break;
                    }
                }

                //往右扫描
                curIndex = midIndex;
                while(true) {
   
     
                    curIndex = curIndex + 1;
                    if(curIndex == arrs.length) {
   
     
                        break;
                    }else {
   
     
                        if(arrs[curIndex] == searchValue) {
   
     
                            indexs.add(curIndex);
                            continue;
                        }
                        break;
                    }
                }
            }

        }

        Integer[] indexss = new Integer[indexs.size()];
        return indexs.toArray(indexss);

    }

    public static void main(String[] args) {
   
     
        int[] arrs = {
   
     1,1,2,3,3,3,3,3,3,4,5,6,7};

        String str = Arrays.toString(search(arrs,0, arrs.length-1, 3));

        System.out.println(str);

    }

}

 

4. 斐波那契(黄金分隔)查找 - 有序的元素组

思路:跟二分查找类似 - 重要:将分割的两部分之间的长度比是黄金分割比即可 - 而Fibonacci数组相临两元素又无限接近黄金分割比 - 故将Fibonacci与黄金分割结合使用

# 二分查找midIndex
midIndex = (left+right)/2

# 黄金分隔查找midIndex
# 斐波那契数组相邻元素之间的比无限接近 黄金分割比0.618
# 重要:将分割的两部分之间的长度比是黄金分割比即可

fibo(k) = fibo(k-1) + fibo(k-2)
# 二分法的思想就是找中心点进行比较 - 因为中心点占了一个位置故 左右总长度 fibo(k) -1
fibo(k) - 1 = ( fibo(k-1)-1 ) + ( fibo(k-2)-1 ) + 1

# 左边部分元素长度 = ( fibo(k-1)-1 ) 
# 右边部分元素长度 = ( fibo(k-2)-1 )
# 中心元素占一个位置 1

 

package top.linruchang.algorithm.search;

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

/**
 * @Classname FibonacciSearch
 * @Description
 * @Date 2022/4/11 13:32
 * @Created by lrc
 */
public class FibonacciSearch {
   
     

    // 返回斐波那契数列第index个位置的数字
    public static int fiboNum(int index) {
   
     

        if (index == 1 || index == 2) {
   
     
            return 1;
        } else {
   
     
            return fiboNum(index - 1) + fiboNum(index - 2);
        }

    }
    /**
     * @param maxValue 斐波那契数列最后一个元素 大于 等于该元素
     * @return
     */
    public static Integer[] fibonacci3(int maxValue) {
   
     

        List<Integer> fiboList = new ArrayList<>();

        int length = 1;
        while (true) {
   
     
            int fiboNum = fiboNum(length);
            fiboList.add(fiboNum);

            if (fiboNum >= maxValue)
                break;
            length++;
        }

        Integer[] fiboNums = new Integer[fiboList.size()];

        return fiboList.toArray(fiboNums);

    }


    /**
     *
     * @param arrs
     * @param searchValue
     * @return 如果最后返回null,说明没找到寻找元素的索引
     */
    public static Integer[] search(Integer[] arrs, int searchValue) {
   
     

        //存储找到的索引
        List<Integer> indexs = new ArrayList<Integer>(arrs.length);
        int left = 0;
        int right ;
        int midIndex;

        int k; //斐波那契的索引

        // 每个元素代表元素长度 -- fibonacci3最后一个元素代表 copyArr数组必须符合的数组长度。 -
        Integer[] fibonacci3 = fibonacci3(arrs.length);
        // 查看fibonacci3全部元素
        System.out.printf("fibonacci数组:%s\n",Arrays.toString(fibonacci3));

        //  fibonacci3[K] 代表当前部分的长度
        k = fibonacci3.length-1;
        right = fibonacci3[k];

        //构成成fibonacci3[K]长的数组 - 不符合则直接用arrs最后一个元素进行填充
        Integer[] copyArr = Arrays.copyOf(arrs, fibonacci3[k]);
        int index = arrs.length;
        while (true) {
   
     
            if (copyArr.length == index)
                break;
            copyArr[index] = arrs[arrs.length-1];
            index++;
        }
        System.out.println("拷贝的数组:" + Arrays.toString(copyArr));
        //数组索引小于0直接退出循环,说明找不到了
        while(k != 0) {
   
     

            midIndex = left + fibonacci3[k-1];
            
            //准备右部分开始比较
            if(copyArr[midIndex] < searchValue) {
   
     
                left = midIndex + 1;
                k-=2;

            //准备左部分开始比较
            }else if(copyArr[midIndex] > searchValue) {
   
     
                right = midIndex - 1;
                k--;
            }else {
   
     

                if(midIndex >= arrs.length-1) {
   
     
                    midIndex = arrs.length-1;
                }
                indexs.add(midIndex);
                int currentIndex = midIndex;
                //往左寻找
                while (true) {
   
     
                    currentIndex = currentIndex - 1;
                    if (currentIndex < 0)
                        break;
                    if (arrs[currentIndex] == searchValue) {
   
     
                        indexs.add(currentIndex);
                    } else {
   
     
                        break;
                    }
                }

                //往右寻找
                currentIndex = midIndex;
                while (true) {
   
     
                    currentIndex = currentIndex + 1;
                    if (currentIndex == arrs.length)
                        break;
                    if (arrs[currentIndex] == searchValue) {
   
     
                        indexs.add(currentIndex);
                    } else {
   
     
                        break;
                    }
                }

                break;
            }

        }

        if(indexs.size() == 0) {
   
     
            return null;
        }
        Integer[] indexss = new Integer[indexs.size()];
        return indexs.toArray(indexss);
    }

    public static void main(String[] args) {
   
     
        Integer[] a = {
   
     4, 5, 10,  15, 24, 36,36};
        
        System.out.printf("原数组:%s\n" , Arrays.toString(a));

        System.out.printf("寻找到的元素索引:%s",Arrays.toString(search(a, 36)));
    }

}