数据结构与算法JAVA版

1.2二分查找

Basic
需求：在有序数组A内，查找值target

  • 如果找到返回索引
  • 如果没有找到返回-1
算法描述
前提 给定一个内含n个元素的有序数组A，满足A0<A1<A2···An-1，一个待查值target
1 设置i=0，j=n-1
2 如果i>j，结束查找，没找到
3 设置m=floor(i+j/2)，m为中间索引，floor 是向下取整 (<=i+j/2的最小整数)
4 如果target<A[m]设置j=m-1，跳到第2步
5 如果A[m]<target设置i=m+1，跳到第2步
6 如果A[m]=target，结束查找，找到了 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//A为有序数组，target为待查找值
//找到返回索引，没找到返回-1
public static int binarySearchBasic(int[] A, int target) {
    int i = 0, j = A.length - 1;//设置指针和初值
    while (i <= j) {//i~j范围内有东西
        int m = (i + j) / 2;
        if (target < A[m]) {//目标在左边
            j = m - 1;
        } else if (A[m] < target) {//目标在右边
            i = m + 1;
        } else {
            return m;
        }
    }
    return -1;
}
// 问题1：为什么i<=j 意味着区间内有未比较的元素，而不是i<j？
// i==j意味着i,j他们指定的元素也会参与比较
// 问题2：(i+j)/2有没有问题？