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

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;
    }
}

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;
        }
    }
}

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;
    }
}