二分查找的分析与应用
看leetcode一道题
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
该题可以使用前缀和+二分查找解决，时间复杂度为
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)。
答案：
public class PrefixSum {
public static void main(String[] args) {
//给定一个正整数数列
int[] nums=new int[]{1,1,1,1,1,1,1,1};
PrefixSum prefixSum = new PrefixSum();
System.out.println(prefixSum.minSubArrayLen(nums,11));
}
public int minSubArrayLen(int[] nums, int target){
int[] sums=Sum(nums);
int sumsMin=Integer.MAX_VALUE;
for(int i=0;i<sums.length;i++){
int tar=sums[i]+target;
int boundary=binarySearch(sums,tar);
if(boundary>0) {
sumsMin = Math.min(sumsMin, boundary - i);
}
}
return sumsMin==Integer.MAX_VALUE?0:sumsMin;
}
// 求前缀和, 该前缀和是升序的
public int[] Sum(int[] nums){
int sum=0;
int[] sums=new int[nums.length+1];
sums[0]=0;
//使用一次遍历求出数组nums的前缀和其中sums[i]表示nums[0]到nums[i-1]的和
for(int i=0;i<nums.length;i++){
sum+=nums[i];
sums[i+1]=sum;
}
return sums;
}
//前提保证数组是升序的
//使用二分查找前缀和中第一个>=sums[i]+target的元素
public int binarySearch(int[] sums,int tar){
int left=0;
int right=sums.length-1;
if(sums[right]>=tar) {
while (left < right) {
int mid = left + (right - left) / 2;//最终的mid总是等于left
if (sums[mid] < tar) {//最终该判断为真，left==right，返回结果
left = mid + 1;
} else {
right = mid;//将>=target的下标放在右边界，结束时该边界就是结果
}
}
return left;
}
return -1;
}
}
二分查找
1.
1.
1. 二分查找的前提：要求数组为有序数组，一般为升序；数组中允许有重复元素；
2.
2.
2. 二分法有三个指针，分别是：
l
e
f
t
left
left、
r
i
g
h
t
right
right、
m
i
d
mid
mid，顾名思义；
3.
3.
3. 最后一次循环，
l
e
f
t
+
1
=
=
r
i
g
h
t
left+1==right
left+1==right;
m
i
d
=
=
l
e
f
t
mid==left
mid==left;
r
i
g
h
t
right
right一直捕获符合条件的元素；最终返回的其实是
r
i
g
h
t
right
right；
2.
2.
2. 实现二分查找代码：
public int binarySearch(int[] sums,int tar){
int left=0;
int right=sums.length-1;
if(sums[right]>=tar) {
while (left < right) {
int mid = left + (right - left) / 2;//最终的mid总是等于left
if (sums[mid] < tar) {//最终该判断为真，left==right，返回结果
left = mid + 1;
} else {
right = mid;//将>=target的下标放在右边界，结束时该边界就是结果
}
}
return left;
}
return -1;
}
上面代码可以查找给定数组 s u m s sums sums中第一个 > = >= >=给定数 t a r tar tar的元素，并返回数组下标，当数组中没有 > = >= >=给定数 t a r tar tar的元素时返回-1；
源码分析
1. 1. 1. 源码比上面代码多了一个以取反的形式返回一个数组中不存在的元素的位置，该位置处于第一个 > = >= >=给定数 t a r tar tar的元素的相邻左边；
private static int binarySearch0(int[] a, int fromIndex, int toIndex,
int key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
如果数组中不存在目标元素，则返回第一个>目标元素的元素位置，这个位置是以反数的形式返回：-(low+1)取反后为low.
感想：感觉leetcode这道题给定的数组的元素可以是自然数，也就是说可以有为0的元素。