二分法小结
程序员文章站
2022-06-03 13:57:28
...
一个基础模板:
注解:
1、mid的表达式之所以不写成mid=(start+end)/2;是因为start+end值可能溢出,而mid=start+(end-start)/2绝对没有溢出的可能,这是一种严谨。
2、while里面的条件是(start+1<end)是因为这样子结束的时候start和end大部分是一左一右情况,也可能是重合的情况。
二分法模板的四点要素
• start+1<end
• start + (end - start) / 2
• A[mid] ==, <, >
• A[start] A[end] ? target
第一题:
public class Solution {
/**
* @param A: an integer sorted array
* @param target: an integer to be inserted
* @return: An integer
*/
public int searchInsert(int[] A, int target) {
// write your code here
if(A==null||A.length==0)
return 0;
int size = A.length;
int left = 0;
int right = A.length-1;
//找比target小的第一个元素
while(left+1<right){
int mid = left + (right - left)/2;
if(A[mid]==target){
right = mid;
}else if(A[mid]>target){
right = mid;
}else{
left= mid;
}
}
if(A[left]>=target)
return left;
if(A[right]<target)
return right+1;
if(A[left]<target&&A[right]>=target)
return left+1;
return -1;
}
}
第二题:
https://www.lintcode.com/problem/find-peak-element/description
思路:
找中间的数,与他相邻的两个数比较。如果mid<mid-1,则证明前半段一定有峰值;如果mid<mid+1,则后半段有。若mid>mid-1&&mid>mid+1,则直接返回.
public class Solution {
/*
* @param A: An integers array.
* @return: return any of peek positions.
*/
public int findPeak(int[] A) {
if(A==null||A.length==0)
return -1;
int begin = 1;
int end = A.length-2;
int mid = 0;
while(begin+1<end){
mid = begin +(end-begin)/2;
if(A[mid]<A[mid+1])
begin = mid;
else if(A[mid]<A[mid-1])
end = mid;
else
return mid;
}
if(A[begin]>A[end]){
return begin;
}else
return end;
}
}
第三题:复原翻转数组
思路:三部翻转法。
如 4 5 1 2 3
第一步 4 5 1 2 3
第二步 5 4 3 2 1
第三步 1 2 3 4 5
注意:如果数组里面有重复数的话,getFirstIndex就不能用二分.
https://www.lintcode.com/problem/recover-rotated-sorted-array/description
上一篇: Javascript实现base64的加密解密方法示例
下一篇: ionic 自定义弹框效果