【二分查找专题】给出四种二分查找的模板
本问题对应课程链接：剑指offer刷题第六期
本次打卡的任务很简单，就是给出四种变形二分查找的模版代码，并且给出了对应的方法名字。
比如对于一个有序数组
arr = [1，2，3，3，3，4，5，5，7]，target = 3，那么
1.寻找第一个大于 target 的元素的下标，本案例中4 就是第一个大于 target 的元素 ，下标 = 5。
对应方法名格式为
int upper(int[] arr, int target){
//如果都不存在，则返回-1
}
2.如果数组中存在元素等于 target，则返回最后一个等于target 的元素下标，如果不存在，则返回第一个大于 target 的元素下标。本案例中最后一个等于target的下标 = 4。
对应方法名
int floor_upper(int[] arr, int target){
//如果都不存在，则返回-1
}
3.寻找最后一个小于 target 的元素的下标，本案例中 2 则是最后一个小于 target 的，下标 = 1.
对应方法名格式为
int lower(int[] arr, int target){
//如果都不存在，则返回-1
}
4.如果数组中存在元素等于 target，则返回第一个等于target 的下标，如果不存在，则返回最后一个小于 target 的元素的下标。本案例中第一个等于target的下标 = 2。
对应方法名格式为
int floor_lower(int[] arr, int target){
//如果都不存在，则返回-1
}
注意：大家给了模版之后，选择一个适合自己的模版，以后都用这个模版，忘了怎么办？这玩意的区别就是要么是大于，要么是大于等于，你如果记混了，可以随便找一组数据试一下，就能分辨出来了，我笔试时都这样干，，，
答案来了，具体答案看这篇文章：4种二分查找模版讲解
shuaidi
共以下 19 个回答
class Solution {
public int[] searchRange(int[] nums, int target) {
int n = nums.length;
int[] ans = new int[2];
}
时间复杂度
四种二分查找四种情况
1、查找大于匹配的第一个元素
2、查找最后一个等于匹配的元素，如果找不到找到大于匹配的元素
3、查找小于匹配的最后一个元素
4、查找第一个匹配的元素，如果找不到则找小于匹配元素的元素
int l = 0, r = arr.size() – 1;
if(nums[r] <= target) return -1;
while(l < r){
int mid = l + r >> 1;
if(arr[mid] > target){
//[l,mid]
r = mid;
}
else if(arr[mid] target){
//(mid,r]
l = mid + 1;
}
else{
//(mid,r]
l = mid + 1;
}
return l;
}
//先找第一个大于的，然后看前一个。
int l = 0, r = arr.size() – 1;
if(nums[r] <= target) return -1;
while(l < r){
int mid = l + r >> 1;
if(arr[mid] > target){
//[l,mid]
r = mid;
}
else if(arr[mid] target){
//(mid,r]
l = mid + 1;
}
else{
//(mid,r]
l = mid + 1;
}
if(nums[l – 1] target && l > 0) return l – 1;
return l;
}
int l = 0, r = arr.size() – 1;
if(nums[r] <= target) return -1;
while(l < r){
int mid = l + r >> 1;
if(arr[mid] > target){
//[l,mid)
r = mid – 1;
}
else if(arr[mid] target){
//[l, mid)
r = mid – 1;
}
else{
//[l,mid]
l = mid;
}
return l;
}
int l = 0, r = arr.size() – 1;
if(nums[r] <= target) return -1;
while(l < r){
int mid = l + r >> 1;
if(arr[mid] > target){
//[l,mid)
r = mid – 1;
}
else if(arr[mid] target){
//[l, mid)
r = mid – 1;
}
else{
//[l,mid]
l = mid;
}
if(arr[l + 1] target && l < arr.size()) return l + 1;
return l;
}
思路:
如果是找第一个则向下取整，mid = left + (right- left)/2
如果是找最后一个则向上取整，mid = left +（right -left +1）/2
打卡
打卡
https://leetcode.cn/problems/binary-search/solutions/2689889/er-fen-mo-ban-pu-tong-zuo-bian-jie-you-b-j1qu
//第一种
class Solution {
public int search(int[] nums, int target) {
int begin = 0;
int end = nums.length – 1;
while(begin <= end){
int mid = (end + begin)/2;
if(target nums[mid])
return mid;
if(target > nums[mid])
begin = mid + 1;
else
end = mid – 1;
}
return -1;
}
}
//第二种
class Solution {
public int search(int[] nums, int target) {
int begin = 0;
int end = nums.length – 1;
while(begin <= end){
int mid = (end + begin)/2;
if(target nums[mid])
break;
if(target > nums[mid])
begin = mid + 1;
else
end = mid – 1;
}
return mid>=nums.length ? -1 : mid+1;
}
}
//第三种
class Solution {
public int search(int[] nums, int target) {
int begin = 0;
int end = nums.length – 1;
while(begin <= end){
int mid = (end + begin)/2;
if(target nums[mid])
break;
if(target > nums[mid])
begin = mid + 1;
else
end = mid – 1;
}
return mid<1 ? -1 : mid - 1;
}
}
//第四种
class Solution {
public int search(int[] nums, int target) {
int begin = 0;
int end = nums.length - 1;
while(begin <= end){ int mid = (end + begin)/2; if(target == nums[mid]) return mid; if(target > nums[mid])
begin = mid + 1;
else
end = mid – 1;
}
return mid<1 ? -1 : mid – 1;
}
}
打卡
“` c++
package BanarySort;
import java.util.*;
public class BanarySort {
public static void main(String[] args) {
int[] arr = new int[]{1, 2,3,3,3,4,5,5,7};
int target = 3;
// int index = upper(arr, target);
// int index = floor_upper(arr, target);
// int index = lower(arr, target);
int index = floor_lower(arr, target);
System.out.println(“index = “+ index + “, value = ” + arr[index]);
}
}
“`
代码
“`c++& vec, int target) { & vec, int target){ & vec, int target) { & vec, int target) {
int Upper(vector
int len = vec.size();
if (len == 0) return -1;
int start=0, end=len-1, mid;
while (start <= end) { mid = (start+end)/2; if (vec[mid] <= target) start = mid + 1; else end = mid - 1; } return start >= len ? -1 : start;
}
int floor_upper(vector
int len = vec.size();
if (len == 0) return -1;
int start = 0, end = len-1, mid;
while (start <= end) { mid = (start + end) / 2; if (vec[mid] == target) break; else if (vec[mid] < target) start = mid + 1; else end = mid - 1; } if (vec[mid] == target) { while (vec[mid] == target) mid++; return mid - 1; } return start >= len ? -1 : start;
}
int Lower(vector
int len = vec.size();
if (len == 0 ) return -1;
int start = 0, end = len – 1, mid;
while (start <= end) { mid = (start + end) / 2; if (vec[mid] >= target) end = mid – 1;
else start = mid + 1;
}
return start – 1;
}
int floor_lower(vector
int len = vec.size();
if (len == 0 ) return -1;
int start = 0, end = len – 1, mid;
while (start <= end) { mid = (start + end) / 2; if (vec[mid] == target) break; else if (vec[mid] > target) end = mid – 1;
else start = mid + 1;
}
if (vec[mid] == target) {
while (vec[mid] == target) mid–;
return mid + 1;
}
return start – 1;
}
“`
class Solution {& nums, int target) {
public:
int search(vector
int low = 0,high = nums.size()-1;
while(low<=high){
int q = (high-low)/2 + low;
if(nums[q]<target){
low = q + 1;
}
else if(nums[q]>target){
high = q – 1;
}
else{
return q;
}
}二分模板进行修改。尽量二分的模板内少加逻辑判断。二分只负责找数字，外面判断即可
return -1;
}
};
C++
//第一个问题
int upper(int[] arr, int target)
{
int left = 0;
int right = arr.size() – 1;
//特殊情况
if(target >= arr[right])
{
return -1;
}
while(left < right)
{
int mid = (right – left)/2 + left;
if(target > arr[mid])
{
left = mid + 1;
}
else if(target < arr[mid])
{
right = mid;
}
else
{
left = mid + 1;
}
}
return left;
}
//第二个问题
int floor_upper(int[] arr, int target)
{
int left = 0;
int right = arr.size() – 1;
//特殊情况
if(target > arr[right])
{
return -1;
}
while(left < right)
{
int mid = (right – left)/2 + left;
if(arr[mid] > target)
{
right = mid;
}
else if(arr[mid] < target)
{
left = mid + 1;
}
else //arr[mid] = target
{
left = mid + 1;
}
}
//判断一下前面的元素是不是最后一个大小等于target的
if(left – 1 >= 0 && arr[left – 1] target)
{
return left – 1;
}
return left;
}
//第三个问题
int lower(int[] arr, int target)
{
int left = 0;
int right = arr.size() – 1;
//特殊情况
if(arr[0] >= target)
{
return -1;
}
while(left < right)
{
int mid = (right – left)/2 + left;
if(target > arr[mid])
{
left = mid;
}
else if(target < arr[mid])
{
right = mid – 1;
}
else
{ //target mid
right = mid – 1;
}
return left;
}
}
//第四个问题
int floor_lower(int[] arr, int target)
{
int left = 0;
int right = arr.size() – 1;
//特殊情况
if(arr[0] > target)
{
return -1;
}
while(left > right)
{
int mid = (right – left)/2 + left;
if(target > arr[mid])
{
left = mid;
}
else if(target < arr[mid])
{
right = mid – 1;
}
else
{ //target = arr[mid]
right = mid – 1;
}
}
//判断下一个元素是否等于target
if(left + 1 < arr.size() && arr[left + 1] target && arr[left] != target)
{
return left +1;
}
return left;
}
思路：在二分模版里面修改返回的条件即可
public static int upper(int[] arr, int target){
int r=arr.length-1;
int l=0;
if(arr[r]<=target) return -1;
while(l<r){
int mid=(r-l)/2+l;//避免i+j溢出
if(arr[mid]>target){
r=mid;
}else if(arr[mid]target){
l=mid+1;
}else{
l=mid+1;
}
}
return l;
}