1 目的

二分查找是目前在目标数组有序的情况下,查找算法中时间复杂度最低的,可以达到NlogN.

2 实现

二分查找的原理是先从数列中间开始查找,如果比中间元素小则在前半段继续查找,如果比中间元素大,则在后半段继续查找,直到目标找到为止。

public class BinarySearch {

    public static int search(int target,Integer[] sourceItems, int low, int high){
        if(low > high)
            return -1;
        int mid = low + (high - low) / 2;
        if(target > sourceItems[mid]){
            return search(target, sourceItems, mid + 1, high);
        }else if(target < sourceItems[mid]){
            return search(target, sourceItems, low, mid - 1);
        }else{
            return mid;
        }

    }

    public static void main(String[] args) {
        int target = 7;
        Integer[] sourceItems = new Integer[]{2, 7, 66};
        int found = search(target, sourceItems, 0, sourceItems.length - 1);
        System.out.println(found);
    }
}