算法时空第7讲 二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Test
{
    //原数组
    private static int[] arr = {10,11,12,16,18,23,29};
    //要查找的key
    private static int key = 17;
    //返回查找的索引
    private static int index;
    //二分查找
    public static void main(String[] args) {
        int[] arr = {10,11,12,16,18,23,29};
        search(0,arr.length);
        System.out.println(index);
    }

    public static void search(int left, int right){
        //int mid = (left + right)/2;
        int mid = left + (right-left)/2;//防止栈溢出

        //注意此处判断，如果不加这个判断。
        //当要查找的数不存在与这个数组，那么就会陷入死循环
        if(left < right){
            if(key < arr[mid]){
                search(left,mid-1);
            }else if(arr[mid] <key){
                search(mid+1,right);
            }else {
                index = mid;
            }
        }else{
            //此处还可以优化，比较key与 arr[left]和arr[right]的差距
            //选取最小的作为index
            index = left;
        }
    }
}