二分查找基础版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 二分查找基础版
 * @param a-待查找的升序数组
 * @param target-待查找的目标值
 * @return
 *      找到返回索引
 *      找不到返回-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) >>> 1;      //修改(i + j) / 2
        if (target < a[m]) {        //目标在左边
            j = m - 1;
        } else if ((a[m] < target)) {//目标在右边
            i = m + 1;
        } else {                    //找到了
            return m;
        }
    }
    return -1;
}

思考一：为什么是i <= j 意味着区间内有未比较的元素，而不是i < j ?
i,j 它们指向的元素也会参与比较，加不加跟j的取值有关系，基础版的j范围是参与比较的既是边界又参与查找，而后面的进阶版直接等于数组长度则不参与查找

思考二：(i+j)/2 有没有问题 ?
超过int的取值就会报错，Java中都是带符号的二进制数，最高位代表符号位，1代表负数，反码需要反转再加一
同一个二进制数 1011_1111_1111_1111_1111_1111_1111_1110
不把最高位视为符号位：代表3221225470
把最高位看成符号位：代表-1073741826
解决办法： >>> 1 无符号右移相当于除以2，不会出现上述的情况，右移二进制数结果是一样的不管正负
举例：-1073741826和3221225470的二进制数完全一致，通过右移运算符得到的十进制数是完全一致的

思考三：都写成小于号有什么好处
代码习惯，数字小的写在左边，数字大的写在右边，思维习惯。

二分查找改动版(优化)

修改后的优势：
1、减少了两次加法运算，加快算法速度，对于庞大的数据来说简直省了不知道多少时间
2、写的少了哈哈哈
注意事项：
1、每一处改动都至关重要，重点是j等于数组长度后不再参与查找数据的作用，只有边界作用
2、while循环里面不能有等于，否则查找不存在的数据时候会出现死循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 二分查找改动版
 * @param a-待查找的升序数组
 * @param target-待查找的目标值
 * @return
 *      找到返回索引
 *      找不到返回-1
 */
public  static int binarySearchAlternative(int[] a,int target ){
    int i = 0, j = a.length;   //第一处改动
    while (i < j) {                //第二处改动
        int m = (i + j) >>> 1;
        if (target < a[m]) {        
            j = m;                  //第三处改动
        } else if ((a[m] < target)) {
            i = m + 1;
        } else {                    
            return m;
        }
    }
    return -1;
}

二分查找-if平衡版

基础版的问题是往左找元素和向右找元素不平衡，查找的次数不一样

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
/**
 * if平衡版二分查找(减少循环次数)
 * 1、左闭右开区间，i指向的可能是目标，而j指向的不是目标
 * 2、不在循环内找出，等范围内只剩i时，退出循环，在循环外比较a[i]与target
 * 3、循环内的平均比较次数减少了
 * 4、时间复杂度@(log(n))
 *
 * @param a
 * @param target
 * @return
 */
public static int binarySearch3(int[] a, int target) {
    int i = 0, j = a.length;
    while (i < j - i) {
        int m = (i + j) >>> 1;
        if (target < a[m]) {
            j = m;
        } else {    //这里的else包括了目标值在中间值的右边以及和中间值相等的情况
            i = m;
        }
    }
    if (a[i] == target) {
        return i;
    } else {
        return -1;
    }
}

二分查找-LeftRightmost

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 二分查找 寻找相同数字靠左的索引(Leftmost)
 * Params:a-待查找的升序数组
 *        target-待查找的目标值
 *
 */
public static int binarySearchLeftmost(int[] a, int target) {
    int i = 0, j = a.length - 1;
    int candidate = -1;
    while (i <= j) {
        int m = (i + j) >>> 1;
        if (target < a[m]) {
            j = m - 1;
        } else if (a[m] < target) {
            i = m + 1;
        } else {
            //记录候选位置
            candidate = m;
            j = m - 1;  //重点
        }
    }
    return candidate;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 二分查找 寻找相同数字靠右的索引
 */
public static int binarySearchRightmost(int[] a, int target) {
    int i = 0, j = a.length - 1;
    int candidate = -1;
    while (i <= j) {
        int m = (i + j) >>> 1;
        if (target < a[m]) {
            j = m - 1;
        } else if (a[m] < target) {
            i = m + 1;
        } else {
            //记录候选位置
            candidate = m;
            i = m + 1;  //重点
        }
    }
    return candidate;
}

二分查找-LeftRightmost(改变返回值变更实际)

找到的情况，返回的是与目标值相同的且最靠左的位置
没找到的情况，返回的是比目标值大的且最最靠左的位置(大于等于目标的最靠左的索引位置)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * 二分查找 寻找相同数字最靠左的索引(优化版)
 */
public static int binarySearchLeftmost2(int[] a, int target) {
    int i = 0, j = a.length - 1;
    int candidate = -1;
    while (i <= j) {
        int m = (i + j) >>> 1;
        if (target <= a[m]) {   //小于等于中间值都要继续向左找
            j = m - 1;
        } else {
            i = m + 1;
        }
    }
    return i;   //这个i返回的是>=target最靠近它的索引位置
}

找到的情况，返回的是与目标值相同的且最靠右的位置
没找到的情况，返回的是比目标值小的且最最靠右的位置(小于等于目标的最靠右的索引位置)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * 二分查找 寻找相同数字靠右的索引(优化)
 */
public static int binarySearchRightmost2(int[] a, int target) {
    int i = 0, j = a.length - 1;
    int candidate = -1;
    while (i <= j) {
        int m = (i + j) >>> 1;
        if (target < a[m]) {    
            j = m - 1;      
        } else {                //大于等于中间值都要继续向左找
            i = m + 1;
        }
    }
    return i - 1;//这个i返回的是<=target最靠近它的索引位置
}

力扣题号

34、35、704