社交网站开发语言,基础建设的网站有哪些内容,湖南医院响应式网站建设企业,肉山谷英雄传说新手任务登录英文网站怎么做问题1#xff1a;使用mid left(right-left)/2 或者 mid (leftright)/2,两者计算结果相同吗#xff1f; 在大多数情况下是等价的。
mid left (right - left) / 2#xff1a;先计算了区间长度#xff0c;然后再除以2。
这种方式可以避免整数溢出问题#xff0c;因为它… 问题1使用mid left(right-left)/2 或者 mid (leftright)/2,两者计算结果相同吗 在大多数情况下是等价的。
mid left (right - left) / 2先计算了区间长度然后再除以2。
这种方式可以避免整数溢出问题因为它可以确保 (right - left) 的结果不会超出整数范围。
mid (left right) / 2直接将左右边界相加然后除以2。
在某些情况下可能会导致整数溢出特别是当 left 和 right 都很大的时候相加的结果可能会超出整数范围。
所以推荐使用mid left (right - left) / 2不会产生整数溢出问题。 问题2while (left right) 和 while (left right) 怎么选择 下面的代码模板都是取等的情况所以会额外有一个越界的判断个人认为采用一样的模板不容易混淆 就按取等加额外判断来做吧。 查找左边界 public class BinarySearch {public int findLeftBound(int[] nums, int target) {int left 0;int right nums.length - 1;while (left right) {int mid left (right - left) / 2;if (nums[mid] target) {// 如果当前中间元素等于目标值则继续向左搜索right mid - 1;} else if (nums[mid] target) {// 如果当前中间元素小于目标值则向右搜索left mid 1;} else {// 如果当前中间元素大于目标值则向左搜索right mid - 1;}}// 如果 left 越界或者 nums[left] 不等于 target则表示 target 不在数组中if (left nums.length || nums[left] ! target) {return -1;}return left;}public static void main(String[] args) {BinarySearch binarySearch new BinarySearch();int[] nums {1, 2, 2, 2, 3, 4, 5};int target 2;int leftBound binarySearch.findLeftBound(nums, target);System.out.println(左边界索引 leftBound);}
} 查找右边界 public class BinarySearch {public int findRightBound(int[] nums, int target) {int left 0;int right nums.length - 1;while (left right) {int mid left (right - left) / 2;if (nums[mid] target) {// 如果当前中间元素等于目标值则继续向右搜索left mid 1;} else if (nums[mid] target) {// 如果当前中间元素小于目标值则向右搜索left mid 1;} else {// 如果当前中间元素大于目标值则向左搜索right mid - 1;}}// 如果 right 越界或者 nums[right] 不等于 target则表示 target 不在数组中if (right 0 || nums[right] ! target) {return -1;}return right;}public static void main(String[] args) {BinarySearch binarySearch new BinarySearch();int[] nums {1, 2, 2, 2, 3, 4, 5};int target 2;int rightBound binarySearch.findRightBound(nums, target);System.out.println(右边界索引 rightBound);}
}
