【手撕数据结构】二分查找(好多细节)
🌈键盘敲烂，年薪30万🌈
目录
普通版本的二分查找：
right只负责控制边界(少了两次比较)：
时间复杂度更稳定的版本：
BSLeftmost：
BSRightmost：
普通版本的二分查找：
- 🏸细节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;}
}