二分系列(二分查找)9/12

一、分情况讨论

1.左闭右闭:[left,right]

因为是左闭右闭，所以left和right都能直接取到。

#这里将>=放到一起，当nums[mid]>=target的时候，
要更新右边界，right=mid-1,这样就把一些相同的情况也切出去了
可以理解为找的第一个为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{right=mid-1;}
}
return left

2.左闭右开:[left,right)

int left=0;
int right=nums.length;
while(left<right){int mid=left+(right-left)/2;if(nums[mid]<target){left=mid+1;}else{right=mid;}
}
return left||right(两个都行)

3.左开右开:(left,right)

int left=-1;
int right=nums.length;
while(left+1<right){int mid=left+(right-left)/2;if(nums[mid]<target){left=mid;}else{right=mid;}
}
return right(两个都行)

二分查找分为四种类型:

大于，大于等于，小于，小于等于; 这四种类型都可以看作是>=,

如果要查找>target的位置的话，可以看成>=(target+1)的位置

如果是查找<target的位置的话，可以看成>=(target)的位置-1

如果是查找<=target的位置的话，可以看成>(target)的位置-1   又因为>(target)可以看作>=target+1

二、在排序数组中查找元素的第一个位置和最后一个位置

思路一：

排序数组->使用二分。第一个位置:>=； 第二个位置:<=

又因为<=target的话可以先看作>target-1    再看作>=(target+1)-1；

所以直接写一个>=的函数

代码一： 

class Solution {public int[] searchRange(int[] nums, int target) {int[] res=new int[]{-1,-1};int start=findPosition(nums,target);//求大于等于targetif(start==nums.length||nums[start]!=target)return res;int end=findPosition(nums,target+1)-1;//求小于等于targetreturn new int[]{start,end};}public int findPosition(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{right=mid-1;}}return left;}
}

思路二：

直接使用>=求第一个元素，然后使用<=求最后一个元素，不需要转换了。

代码二：

class Solution {public int[] searchRange(int[] nums, int target) {int[] res = new int[] { -1, -1 };int start = findFirstPosition(nums, target);// 求大于等于targetif (start == nums.length || nums[start] != target)return res;int end = findLastPosition(nums, target );// 求小于等于targetreturn new int[] { start, end };}public 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) {right = mid - 1;} else {left = mid + 1;}}return left;}public 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){left=mid+1;}else{right=mid-1;}}return right;}
}

三、两个数之间的距离值

题意:

给定两个数组nums1,nums2; 请你返回两个元素间的距离值；

距离值」 定义为符合此距离要求的元素数目：对于元素 arr1[i] ，不存在任何元素 arr2[j] 满足 |arr1[i]-arr2[j]| <= d 。

思路：

使用二分查找：

1.首先将nums2进行排序；

2.然后找到nums2中>=nums1[i]-d的下标；找到<=nums1[i]+d的下标；将<=看成>=(nums[i]+d+1)-1

3.判断下标是否合规。如果不合规说明不存在；合规说明存在。(0,-1)就不合规

代码：

class Solution {public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {Arrays.sort(arr2);int res=0;for(int num:arr1){int left=num-d;int right=num+d;int start=findIndex(arr2,left);int end=findIndex(arr2,right+1)-1;if(start>end)res++;}return res;}public int findIndex(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 {left = mid + 1;}}return left;}
}