搜索

顺序搜索

顺序查找
: 在一个已知无序（或有序）的队列中找出与给定的关键字相同的数的具体位置。

其原理是让关键字与队列中的数从开始一个一个地往后逐个比较，知道找到与给定的关键字相同的数。

package inner.search;

public class SequentialSearch {
    private int[] array;
    public SequentialSearch(int[] array) {
        this.array = array;
    }

    public int search(int key) {
        for(int i = 0; i < array.length; i++) {
            if(array[i] == key){
                return i;
            }
        }
        return -1;
    }

    //优化，防止越界
    public int search2(int key) {
        if(key == array[0]) {
            return 0;
        }
        int temp = array[0];
        array[0] = key;
        int i = array.length - 1;
        while(array[i] != key) {
            i--;
        }
        array[0] = temp;
        if(i == 0) {
            return -1;
        }
        return i;
    }
}

二分查找

二分查找也叫折半查找。二分查找有两个要求：一个是数列有序，另一个是数列使用顺序存储结构（比如数组）。

二分查找的实现

package inner.search;

public class BinarySearch {
    private int[] array;
    public BinarySearch(int[] array) {
        this.array = array;
    }
    public int searchRecursion(int target) {
        if(array != null) {
            return searchRecursion(target, 0, array.length - 1);
        }
        return -1;
    }
    
    public int searchRecursion(int target, int start, int end) {
        if(start > end) {
            return -1;
        }
        int mid = start + (end - start) / 2;
        if(array[mid] == target) {
            return mid;
        } else if(target < array[mid]) {
            return searchRecursion(target, start, mid - 1);
        } else {
            return searchRecursion(target, mid + 1, end);
        }
    }
}