力扣算法题（三）二分查找

力扣算法题（三）二分查找

209-Minimum Size Subarray Sum

给定含有n个正整数的数组，和一个正整数target，找出该数组中满足其和>=target的长度最小的连续子数组，并返回其长度，如果不存在，返回0

//方法有误，暂未查出
public int minSubArrayLen03(int target,int[] nums) {

   int result=0;for(int i=0;i<nums.length;i++) {result+=nums[i];}if(result<target) {return 0;}int i=0,j=nums.length-1;while(i<j) {if(nums[i]<nums[j]) {if(result-nums[i]>=target) {result=result-nums[i];i++;}else {return j-i+1;}}else if(nums[i]>nums[j]){if(result-nums[j]>=target) {result=result-nums[j];j--;}else {return j-i+1;}}else if(nums[i]==nums[j]) {if(result-nums[i]>=target) {if((i+1)<(j-1)) {if((nums[i+1]<nums[j-1])) {result-=nums[i];i++;} else {result-=nums[j];j++;}}else {result-=nums[i];i++;}}else {return j-i+1;}}}return j-i+1;

}

1，暴力法
初始化子数组长度为数组长度，枚举数组中的每个下标作为子数组的开始下标，//对于每个开始下标i，需要找到大于等于i的最小下标j，使得nums[i]到nums[j]的元素和大于等于s
更新数组的最小长度

public int minSubArrayLen04(int s,int[] nums) {int n=nums.length;//特殊情况if(n==0) {return 0;}int ans=Integer.MAX_VALUE;for(int i=0;i<n;i++) {int sum=0;for(int j=i;j<n;j++) {sum+=nums[j];if(sum>=s) {ans=Math.min(ans, j-i+1);break;}}}return ans==Integer.MAX_VALUE?0:ans;//o(n2),o(1)}

2，前缀和+二分查找
为了使用二分查找，需要额外创建一个数组sums用于存储数组nums的前缀和，
其中sums[i]表示从nums[0]到nums[i-1]的元素和。
对每个下标i，通过二分查找得到大于或等于i的最小下标bound，使得sums[bound]-sums[i-1]>=s
更新子数组的最小长度，子数组的长度是bound-(i-1)

public int minSubArrayLen05(int s,int[] nums) {int n=nums.length;if(n==0) {return 0;}int ans=Integer.MAX_VALUE;int[] sums=new int[n+1];//sums[0]=0表示前0个元素的前缀和为0//数组递增，因为为正for(int i=1;i<=n;i++) {sums[i]=sums[i-1]+nums[i-1];}for(int i=1;i<=n;i++) {int target=s+sums[i-1];//也就是target-sums[i-1]=sint bound =Arrays.binarySearch(sums, target);//在sums中搜索值为target的元素，返回索引。// 搜索值不是数组元素，且大于数组内元素，索引值为 – (length + 1);//搜索值不是数组元素，且小于数组内元素，索引值为 – 1。if (bound < 0) {bound = -bound - 1;//length：找不到最后结果会小于0//0     ：找不到的话最后结果会小于0}if (bound <= n) {ans = Math.min(ans, bound - (i - 1));}}return ans == Integer.MAX_VALUE ? 0 : ans;}

//二分查找的时间复杂度是logn，遍历的时间复杂度是n，所以总时间复杂度是O(nlog(n))

3，滑动窗口
定义两个指针start和end分别表示子数组的开始位置和结束位置，
维护sum存储子数组中的元素和，即从nums[start]到nums[end]的元素和
初始，start和end都指向0，sum值为0，
每一轮迭代将nums[end]加到sum，如果sum>=s,则更新子数组最小长度end-start+1
然后将nums[start]从sums中减去并将start右移,直到sum<s,
在此过程中同样更新子数组的最小长度。每一轮迭代最后end右移。

public int minSubArrayLen06(int s,int[] nums) {int n=nums.length;if(n==0) {return 0;}int ans=Integer.MAX_VALUE;int start=0,end=0;int sum=0;while(end<n) {//不够大就一直加sum+=nums[end];while(sum>=s){ans=Math.min(ans, end-start+1);sum-=nums[start];start++;}end++;}return ans==Integer.MAX_VALUE?0:ans;}

704-Binary Search (未找到返回-1)

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

//二分查找，不用仔细看。

public int search(int[] nums,int target) {int n=nums.length;if((nums[0]>target)||(nums[n-1])<target) {return -1;}int i=0;for(i=0;i<n;i++) {if(nums[i]==target) {return i;}}return -1;//循环出来也没找到，说明没有}

//二分查找
//初始化指针left=0,right=n-1 当left<=right
//循环，当left<right
//比较中间元素nums[privot=(left+right)/2]和目标值target
//如果target=nums[pivot],返回pivot
//如果target<nums[pivot],则在右侧继续搜索right=pivot-1
//如果target>nums[pivot],则在右侧继续搜索left=pivot+1

  public int search01(int[] nums,int target) {int n=nums.length;int left=0,right=n-1,pivot=0;while(left<=right) {
//<=因为可能出现只有一个元素的情况pivot=left+(right-left)/2;
//返回中间 位置的下标，判断并进行下一次二分，可以防止right+left可能会溢出if(target==nums[pivot]) {return pivot;}else if(target>nums[pivot]) {//向右侧搜索left=pivot+1;}else {right=pivot-1;}}//出了循环还没找到，说明没有return -1;}

35-Search Insert Position (未找到元素时返回待插入元素的位置，若存在多个目标元素，则返回任意一个) (二分查找避免死循环注意项)

//给定排序数组和目标值，在数组中找到目标值，并返回其索引，如果目标值不存于数组中，返回它将会按顺序插入的位置

   public int searchInsert(int[] nums, int target) {int n=nums.length;//排除，target不在数组范围内if(target<=nums[0])return 0;//比最后一个数大放在n位置if(target>nums[n-1])return n;//和最后一个数相等放在n-1位置if(target==nums[n-1])return n-1;int i=0;while(i<n) {if(nums[i]>=target) {return i;}else{i++;}}return i;}

//暴力解决需要O(n)的时间复杂度，二分的话则可以降低到O(logn)
//思路和二分查找没有区别，设定左侧下标left和右侧下标right中间下标mid
//每次根据nums[mid]和target之间的大小进行判断，相等则直接返回下标
//查找结束没有相等值返回left

模板

    public int searchInsert01(int[] nums,int target) {int left=0,right=nums.length-1;while(left<=right) {//这里=因为可能数组只有一个元素int mid=left+(right-left)/2;//5/2=2if(nums[mid]==target) {}else if(nums[mid]<target) {left=mid+1;//去右边找，从mid+1到right，剔除mid点}else if(nums[mid]>target){right=mid-1;//左边找，从left到mid-1，剔除了mid点}}return 0;}

34-Find First and Last Position of Element in Sorted Array (返回目标元素的左右边界，不存在时则返回{-1,-1}) (34升级)

//34排序数组
//在排序数组中查找该元素在数组中第一个和最后一个的位置
//如果没有返回[-1，1]

//由于数组已经排序，整个数组是单调递增的，使用二分法来加速查找过程
//考虑target的开始位置和结束位置，我们要找的就是数组中，
//第一个等于target的位置和第一个大于target的位置

public int[] searchRange(int[] nums,int target) {int leftIdx=binarySearch(nums,target,true);int rightIdx=binarySearch(nums,target,false)-1;if(leftIdx<=rightIdx&&rightIdx<nums.length&&nums[leftIdx]==target&&nums[rightIdx]==target) {return new int[] {leftIdx,rightIdx};}return new int[] {-1,-1};
}public int binarySearch(int[] nums, int target, boolean lower) {int left=0,right=nums.length-1,ans=nums.length;while(left<right) {int mid=(left+right)/2;if(nums[mid]>target||(lower&&nums[mid]>=target)) {//找第一个等于或者最大的小于它的，找第一个大于它right=mid-1;ans=mid;}else {left=mid+1;}}return 0;
}

//while(left<=right)在退出循环的时候left=right+1,即right在左，left在右
//while(left< right)在退出循环的时候，left==right

//1,找第一次出现的位置，二分查找，找到了继续向左找 2,查找出现的最后一个位置，向右

 public int[] searchRange01(int[] nums,int target) {if(nums.length==0) {return new int[] {-1,-1};}int firstPosition=findFirstPosition(nums,target);int lastPosition=findLastPosition(nums,target);return new int[] {firstPosition,lastPosition};}private int findFirstPosition(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]区间里找right=mid-1;}else if(nums[mid]<target) {//应该继续向右边找，即[mid+1,right]区间里找left=mid+1;}else {//此时 nums[mid]>target,应该继续向左找，即[left,mid-1]区间找right=mid-1;}}//此时left和right位置left=right+1,此时left才是第一次元素出现的位置//因此还需要特别做一次判断if(left!=nums.length&&nums[left]==target) {return left;}return -1;}private int findLastPosition(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) {// 只有这里不一样：不可以直接返回，应该继续向右边找，即 [mid + 1, right] 区间里找left = mid + 1;} else if (nums[mid] < target) {// 应该继