Java中怎么實現(xiàn)一個查找算法

這篇文章將為大家詳細講解有關(guān)Java中怎么實現(xiàn)一個查找算法，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關(guān)知識有一定的了解。

線性查找 (linear search)

public class LinearSearchDemo {
    public static void main(String[] args) {
        int[] data = {2, 1, 4, 6, 12, 7};
        int target = 12;
        int searchIndex = search(data, target);
        if (searchIndex != -1) {
            System.out.println("found at: " + searchIndex);
        }else {
            System.out.println("not found");
        }
    }
    /*
     *@param  data   待查找的數(shù)組
     *@param  target 待查找的值
     *@return int    目標值在數(shù)組中的索引，如果沒找到返回-1
     */
    public static int search(int[] data, int target) {

        int length = data.length;

        //從頭遍歷數(shù)組中的各個值，如果找到目標值就返回其索引
        for (int i = 0; i < length; i++) {
            if (data[i] == target) {
                return i;
            }
        }

        //代碼能走到這一步就說明上面的循環(huán)遍歷結(jié)束了也沒找到目標值
        //即目標值不存在于數(shù)組中
        return -1;

    }
}

二分查找( binary search)

二分查找的關(guān)鍵點其實是數(shù)據(jù)順序的有序，數(shù)據(jù)順序不有序的話，用不了二分查找的

//二分查找：在有序數(shù)組中查找某一特定元素的搜索算法
public class BinarySearch {
    public static void main(String[] args) {
        int[] data = {1, 5, 6, 12, 15, 19, 23, 26, 30, 33, 37, 42, 53, 60};
        int target = 19;
        int index = binarySearch3(data, 0, data.length - 1, target);
        if (index > -1) {
            System.out.println("found ：" + index);
        }else {
            System.out.println("not found");
        }
    }

    /**
     * 遞歸方法實現(xiàn)二分查找
     * @param data   已排序數(shù)組(這里假設(shè)是從小到大排序)
     * @param from   起始位置
     * @param to     終止位置
     * @param target 要查找的值
     * @return 要查找的值在數(shù)組中的位置，如果沒找到則返回-1
     */
    private static int binarySearch2(int[] data, int from, int to, int target) {
        if (from <= to) {
            int mid = from + (to - from) / 2;//中間位置，為了防止溢出使用這種方式求中間位置
            if (data[mid] < target) {//中間的值比目標值小，則在左半邊繼續(xù)查找
                return binarySearch2(data, mid + 1, to, target);
            }else if(data[mid] > target){//中間的值比目標值大，則在右半邊繼續(xù)查找
                return binarySearch2(data, from, mid - 1, target);
            }else {//找到了，把找到的情況放在最后是因為多數(shù)情況下中間值不是大于就是小于，這樣做可以節(jié)省操作
                return mid;
            }
        }
        return -1;
    }

    /**
     * 非遞歸方法實現(xiàn)二分查找
     * @param data   已排序數(shù)組(這里假設(shè)是從小到大排序)
     * @param from   起始位置
     * @param to     終止位置
     * @param target 要查找的值
     * @return 要查找的值在數(shù)組中的位置，如果沒找到則返回-1
     */
    private static int binarySearch3(int[] data, int from, int to, int target) {
        while(from <= to) {
            int mid = from + (to - from) / 2;
            if (data[mid] < target) {
                from = mid + 1;
            }else if(data[mid] > target) {
                to = mid - 1;
            }else {//找到了，把找到的情況放在最后是因為多數(shù)情況下中間值不是大于就是小于，這樣做可以節(jié)省操作
                return mid;
            }
        }
        return -1;
    }
}

關(guān)于Java中怎么實現(xiàn)一個查找算法就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學(xué)到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。