二分法板子
2019-03-13 本文已影响0人
ZalleDay
二分法常常使用,根据统计只用10%的程序员才可以完美写出二分,二分的关键在于对条件、边界的判定,而下面这个模板是一个万能模板,转自知乎。
模板如下,
public int[] searchRange(int[] nums, int target) {
if (nums ==null || nums.length == 0)
return new int[]{-1,-1};
int[] result = new int[2];
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 right = mid;
}
if (nums[left] != target)
return -1;
}
注意的是left最后要进行检验,得到的是第一个target的值。
至于如何证明这个是一个完美模板还需要看原地址的证明。
源地址:https://www.zhihu.com/question/36132386/answer/530313852
博主只是使用java代码重构了一遍。
最后博主使用了这个板子写了两道关于二分的leetcode的题。
第一题 Find First and Last Position of Element in Sorted Array
https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
public int[] searchRange(int[] nums, int target) {
if (nums ==null || nums.length == 0)
return new int[]{-1,-1};
int[] result = new int[2];
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 right = mid;
}
if (nums[left] != target)
return new int[]{-1,-1};
int index1 = left;
for (int i = left; i < nums.length; i++){
if (target == nums[i]) index1 = i;
else break;
}
int index2 = left;
for (int i = left; i >= 0; i--){
if (target == nums[i]) index2 = i;
else break;
}
result [0] = index2; result[1] = index1;
return result;
}
第二题 Search in Rotated Sorted Array
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0)
return -1;
int left = 0;
int right = nums.length -1;
while (left < right){
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < nums[right] ){
if (nums[mid] < target && nums[right] >=target) left = mid + 1;
else right = mid;
}else if (nums[mid] > nums[right]){
if (nums[left] <= target && nums[mid] >target) right = mid ;
else left =mid + 1;
}
}
if(nums[left] == target)
return left;
else
return -1;
}