Java 二分查找

二分查找

代码：

package search;

import java.util.Date;

public class T1 {
    public static void main(String[] args) {
        int[] nums = new int[200000000];
        init_data(nums);
        long startTime = System.nanoTime();
        int index = binarySearch(nums,99999997);
        //int index = normalsearch(nums,99999997);
        long endTime = System.nanoTime();
        System.out.println("index:"+index+"\tuseTime:"+(endTime - startTime)+"ns");
    }

    /**
     * 二分查找也叫折半查找，速度非常的快 平均查找时间：log2(n)
     * @param nums
     * @param key
     * @return
     */
    private static int binarySearch(int[] nums, int key) {
        int low=0,heigh=nums.length-1,mid;
        int count = 0;
        while (low<=heigh){
            mid = (low+heigh)/2;
            if (nums[mid]==key){
                System.out.println(count);
                return mid;
            }
            if (nums[mid]>key){
                heigh = mid-1;
            }else{
                low = mid+1;
            }
            count ++;
        }
        return -1;
    }

    /**
     * 普通查找，通过遍历的方式 平均查找时间：n/2
     * @param nums
     * @param key
     * @return
     */
    private static int normalsearch(int[] nums, int key) {
        int count = 0;
        for (int j = 0; j < nums.length; j++) {
            if (nums[j]==key){
                System.out.println(count);
                return j;
            }
            count ++;
        }
        return -1;
    }
    /**
     * 初始化数组值
     * @param nums
     */
    private static void init_data(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            nums[i] = (i+1)*5-3;
        }
    }
}

运行结果：

二分查找
循环次数：25
index:19999999    useTime:9105200ns

普通查找
循环次数：19999999
index:19999999    useTime:20559600ns