【手撕数据结构】二分查找(好多细节)

简介: 【手撕数据结构】二分查找(好多细节)

🌈键盘敲烂,年薪30万🌈



 

普通版本的二分查找

  • 🏸细节1:循环判定条件是left <= right
  • ⭐细节2:mid = (left + right ) >>> 1 原因见代码注释
 
/***
 * 二分查找的实现 3个版本
 * 时间复杂度:O(longn)
 * 空间复杂度:O(1)
 *
 * 细节1:循环判定条件是left <= right
 * 细节2:mid计算要用 >>> 因为left + right 可能越界
 *      例如:right = Integer.MAX_INT-1 left = 0;
 *      第一轮计算没问题 假设mid < target
 *      left = mid + 1; 这是后left+ right 就超出int的最大范围,变成负数
 *      原因很简单:java没有无符号数,最高位表示符号位,/ 运算是先将补码转原码 >>>位运算是直接再二进制上运算
 */
public class Demo1 {
    public static void main(String[] args) {
        int[] nums = {1,4,6,8,15,76,145};
        int target = 145;
        int index1 = method1(nums, target);
        System.out.println(target + "索引为" + index1);
        System.out.println(target + "索引为" + index2);
    }
 
    private static int method1(int[] nums, int target) {
        int left = 0, right = nums.length-1;
        while(left <= right){
            //细节 用无符号右移运算符
            int mid = (left + right) >>> 1;
            if(nums[mid] > target){
                right = mid - 1;
            }else if (nums[mid] < target){
                left = mid + 1;
            }else{
                return mid;
            }
        }
        return -1;
    }
}

right只负责控制边界(少了两次比较):

  • 改动1:while条件是left < right
  • 改动2:right = nums.length
public class Demo1 {
    public static void main(String[] args) {
        int[] nums = {1,4,6,8,15,76,145};
        int target = 145;
        int index2 = method2(nums, target);
        System.out.println(target + "索引为" + index2);
    }
}
    private static int method2(int[] nums, int target) {
        int left = 0, right = nums.length; //right 只代表有边界,不参与比较
        while(left < right){
            int mid = (left + right) >>> 1;
            if(nums[mid] < target){
                left = mid + 1;
            }else if(nums[mid] > target){
                right = mid;
            }else {
                return mid;
            }
        }
        return -1;
    }

时间复杂度更稳定的版本:

  • 细节:减少了if比较次数
public class Demo1 {
    public static void main(String[] args) {
        int[] nums = {1,4,6,8,15,76,145};
        int target = 145;
        int index3 = method3(nums, target);
        System.out.println(target + "索引为" + index3);
    }
}    
    private static int method3(int[] nums, int target) {
        //这个最牛逼
        //减少循环内的比较次数
        int left = 0, right = nums.length;
        while(1 < right - left){
            int mid = (left + right) >>> 1;
            if(nums[mid] > target){
                right = mid;
            }else{
                left = mid;
            }
        }
        if(nums[left] == target){
            return left;
        }
        return -1;
    }

BSLeftmost:

/**
 *
 * 应用:求成绩排名  求前任
 */
public class Leftmost {
    public static void main(String[] args) {
        int[] nums = {1,2,4,4,4,6,7};
        int target = 3;
        /***
         * params
         * return 找到了 - 返回靠左的下标
         *        没找到 - 返回>target的最靠左下标
         */
        int ans = BSLeftmost(nums, target);
        System.out.println(ans);
 
    }
 
    private static int BSLeftmost(int[] nums, int target) {
        int left = 0, right = nums.length -1;
        while(left <= right){
            int mid = (left+right) >>> 1;
            if(target > nums[mid]){
                left = mid + 1;
            } else{
                right = mid - 1;
            }
        }
        return left;
    }
}

BSRightmost:

/**
 *
 * 求后任
 */
public class Rightmost {
    public static void main(String[] args) {
        int[] nums = {1,2,4,4,4,6,7};
        int target = 3;
        /**
         * return 找到了返回下标
         *        没找到返回 <= targer的最靠右索引
         *
         */
        int ans = BSRightmost(nums, target);
        System.out.println(ans);
    }
 
    private static int BSRightmost(int[] nums, int target) {
        int left = 0, right = nums.length-1;
        while(left <= right){
            int mid = (left + right) >>> 1;
            if(target >= nums[mid]){
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        return left - 1;
    }
}


相关文章
数据结构上机实验之二分查找
数据结构上机实验之二分查找
|
15天前
|
机器学习/深度学习
数据结构实验之查找四:二分查找
数据结构实验之查找四:二分查找
|
15天前
|
算法 JavaScript 前端开发
JavaScript算法和数据结构:写一个二分查找的函数。
JavaScript算法和数据结构:写一个二分查找的函数。
33 0
|
7月前
|
算法
数据结构与算法之经典算法《二分查找》
数据结构与算法之经典算法《二分查找》
23 0
|
8天前
|
算法 索引
【数据结构与算法 | 基础篇】力扣704/35/34:二分查找
【数据结构与算法 | 基础篇】力扣704/35/34:二分查找
|
15天前
|
算法
数据结构-二分查找
数据结构-二分查找
13 1
|
15天前
|
机器学习/深度学习 算法 Java
【数据结构查找算法篇】----二分查找【实战项目】
【数据结构查找算法篇】----二分查找【实战项目】
34 1
|
5月前
|
算法 C语言
从0开始学习数据结构 C语言实现 1.前篇及二分查找算法
从0开始学习数据结构 C语言实现 1.前篇及二分查找算法
39 0
|
8月前
|
算法 Java 索引
Java【数据结构】二分查找
Java【数据结构】二分查找
49 0
|
算法 C++
C++数据结构算法(三)二分查找
C++数据结构算法(三)二分查找
C++数据结构算法(三)二分查找