[数据结构与算法]查找-二分查找

思路：将数组有序排列，确定中间数组下标，在左右查找

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

    public static int binarySearch(int[] arr,int left,int right,int findval){
        int mid = (left+right)/2;
        int minval = arr[mid];
        if (findval > minval){
            return binarySearch(arr, mid+1, right, findval);
        }else if (findval < minval){
            return binarySearch(arr, left, mid-1, findval);
        }else {
            return mid;
        }
    }
}

此时找不存在的会出现死循环

package search;

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

    public static int binarySearch(int[] arr,int left,int right,int findval){
        int mid = (left+right)/2;
        int minval = arr[mid];
        //当left大一right时，说明没有找到
        if (left > right){
            return -1;
        }
        if (findval > minval){
            return binarySearch(arr, mid+1, right, findval);
        }else if (findval < minval){
            return binarySearch(arr, left, mid-1, findval);
        }else {
            return mid;
        }
    }
}

此时数组有相同数时，只能找到一个

思路：找到值不要立马返回，像mid的左边扫描，找到相同值元素下标，加入集合，右边一样

package search;

import java.util.ArrayList;

public class BinarySearch {
    public static void main(String[] args) {
        int arr[] = {1,8,10,15,15,89,1000,1234};
        ArrayList<Integer> list = binarySearch(arr, 0, arr.length, 15);
        System.out.println(list);
    }

    public static ArrayList<Integer> binarySearch(int[] arr, int left, int right, int findval){
        int mid = (left+right)/2;
        int minval = arr[mid];
        //当left大一right时，说明没有找到
        if (left > right){
            return new ArrayList<Integer>();
        }
        if (findval > minval){
            return binarySearch(arr, mid+1, right, findval);
        }else if (findval < minval){
            return binarySearch(arr, left, mid-1, findval);
        }else {
            ArrayList<Integer> resIndex = new ArrayList<>();
            int temp = mid-1;
            while (true){
                if (temp <0 || arr[temp] != findval){
                    break;
                }
                resIndex.add(temp);
                temp -= 1;
            }
            resIndex.add(mid);
            //向右扫描
            temp = mid + 1;
            while (true){
                if (temp > arr.length-1 || arr[temp] != findval){
                    break;
                }
                resIndex.add(temp);
                temp += 1;
            }

            return resIndex;
        }
    }
}

插值查找

二分查找如果找头的数，查找次数较多

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

package search;

public class InsertSearch {
    public static void main(String[] args) {
        int arr[] = new int[100];
        for (int i = 0; i < 100; i++) {
            arr[i] = i + 1;
        }
        int i = insertSearch(arr, 0, arr.length - 1, 8);
        System.out.println(i);
    }
    //公式int mid =left +(right-left)*(findVal-arr[left])/(arr[right]-arr[left])
    public static int insertSearch(int[] arr,int left,int right,int findval){
        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 insertSearch(arr, mid+1, right, findval);
        }else if (findval < midval){
            return insertSearch(arr, left, mid-1, findval);
        }else {
            return mid;
        }
    }
}