国外做旅游攻略的网站好,中国建筑第八工程局官网,有网站怎么做企业邮箱,天元建设集团有限公司破产了吗#x1f308;键盘敲烂#xff0c;年薪30万#x1f308; 目录
普通版本的二分查找#xff1a;
right只负责控制边界(少了两次比较)#xff1a;
时间复杂度更稳定的版本#xff1a;
BSLeftmost#xff1a;
BSRightmost#xff1a; 普通版本的二分查找#xff1a;
… 键盘敲烂年薪30万 目录
普通版本的二分查找
right只负责控制边界(少了两次比较)
时间复杂度更稳定的版本
BSLeftmost
BSRightmost 普通版本的二分查找
细节1循环判定条件是left right⭐细节2mid (left right ) 1 原因见代码注释 /**** 二分查找的实现 3个版本* 时间复杂度Olongn* 空间复杂度O1** 细节1循环判定条件是left right* 细节2mid计算要用 因为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只负责控制边界(少了两次比较)
改动1while条件是left right改动2right 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 (leftright) 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;}
}
