【二分查找专题】给出四种二分查找的模板

本次打卡的任务很简单，就是给出四种变形二分查找的模版代码，并且给出了对应的方法名字。

比如对于一个有序数组

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

更新于 2 年前 138 13

共以下 13 个回答

youngsir 普通 2024年12月17日上午10:23

打卡

#include <iostream>
using namespace std;
#include <vector>
 int upper(vector<int> arr, int target){
        int l = 0,r = arr.size()-1,mid;
        if(target > arr[r]) return -1;
        while(l<r){
            mid = ((r - l)/2)+l;
            if(arr[r] > target){
                r = mid;
            }else{
                l = mid+1;
            }
        }
        return l;
    }
int floorupper(vector<int> arr,int target){
    int l = 0,r = arr.size()- 1,mid;
    if(target > arr[r]) return -1;
    while(l<r){
        mid = ((r-l)/2)+l;
        if(arr[r] > target){
            r = mid;
        }else if(arr[mid] == target){
            l = mid + 1; 
        }
        else{
            l = mid + 1;
        }
        if(l-1>=0&&arr[l-1] == target){
            return l-1;
        }
    }
    return l;
}
int lower(vector<int> arr, int target){
    int l = 0, r = arr.size() - 1,mid;
    if(target  <= arr[l]) return -1;
    while(l < r){
        mid = ((r-l)/2)+l; 
        if(arr[mid] > target){
            r = mid - 1;
        }else if(arr[mid] == target){ 
            r = mid - 1;
        }else{
            l = mid;
        }

    }

    return l;
}
int floorlower(vector<int> arr, int target){
    int l = 0, r = arr.size() - 1, mid;
    if(target < arr[l]) return -1;
    while(l < r){
         mid = ((r-l)/2)+l;
        if(arr[mid] > target){ 
            r = mid - 1;
        }else if(arr[mid] == target){
            r = mid - 1;
        }else{
            l = mid;  
        }
    }
    if(l + 1 < arr.size() && arr[l + 1] == target) return l + 1;
    return l;
}
int main() {
    vector<int> arr = {1,2,3,3,3,4,5,5,7};
    int target = 3;
    cout<<upper(arr,target)<<endl;
    cout<<floorupper(arr,target)<<endl;
    cout<<lower(arr,target)<<endl;
    cout<<floorlower(arr,target)<<endl;
    return 0;
}

0 赞同 0 条回复

秋山丽奈普通 2024年12月10日下午8:11

参照他人代码

class MyBinarySearch{
    // 1. 寻找第一个大于 target 的元素的下标：求 target 的右侧边界（如果存在，返回值 + 1，如果不存在，返回值也 + 1）
    public int upper(int[] arr, int target) {
        int l = 0, r = arr.length - 1;
        // 判断特殊情况
        if(arr[r] <= target){
            return -1;
        }
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (arr[mid] < target) {
                l = mid + 1;
            }else if (arr[mid] > target) {
                r = mid - 1;
            }else {
                // 求的是右侧边界，收缩左侧边界
                l = mid + 1;
            }
        }
        // 此时，l = r + 1，nums[l - 1] 表示的 arr 的右侧边界，如果不存在的话，返回的小于 target 的最大索引
        // 越界判断
        if (l - 1 < 0 || l - 1 >= arr.length) {
            return -1;
        }
        return l;
    }

    // 2. 如果数组中存在元素等于 target，则返回最后一个等于 target 的元素下标，如果不存在，则返回第一个大于 target 的元素下标。
    public int floor_upper(int[] arr, int target){
        int l = 0, r = arr.length - 1;
        // 判断特殊情况
        if(arr[r] <= target){
            return -1;
        }
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (arr[mid] < target) {
                l = mid + 1;
            }else if (arr[mid] > target) {
                r = mid - 1;
            }else {
                // 求的是右侧边界，收缩左侧边界
                l = mid + 1;
            }
        }
        // 此时，l = r + 1，nums[l - 1] 表示的 arr 的右侧边界元素，如果不存在的话，返回的小于 target 的最大索引
        // 越界判断
        if (l - 1 < 0 || l - 1 >= arr.length) {
            return -1;
        }

        return arr[l - 1] == target ? l - 1 : l;
    }

    // 3.寻找最后一个小于 target 的元素的下标：寻找 target 的左侧边界，如果存在的话，返回的是 target 的左侧边界（ 结果-1 即可）；
// 如果不存在的话，返回的是大于 target 的最小索引。（结果-1）
    public int lower(int[] arr, int target) {
        int l = 0, r = arr.length - 1;

        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (arr[mid] < target) {
                l = mid + 1;
            }else if (arr[mid] > target) {
                r = mid - 1;
            }else {
                // 求的是左侧边界，收缩右侧边界
                r = mid - 1;
            }
        }
        // 此时，l = r + 1，nums[l] 表示的 arr 的左侧边界元素，如果不存在的话，返回的大于 target 的最小索引
        // 越界判断
        if (l < 0 || l >= arr.length) {
            return -1;
        }

        return l - 1;
    }


    // 4.如果数组中存在元素等于 target，则返回第一个等于 target 的下标，如果不存在，则返回最后一个小于 target 的元素的下标。
    public int floor_lower(int[] arr, int target) {
        int l = 0, r = arr.length - 1;

        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (arr[mid] < target) {
                l = mid + 1;
            }else if (arr[mid] > target) {
                r = mid - 1;
            }else {
                // 求的是左侧边界，收缩右侧边界
                r = mid - 1;
            }
        }
        // 此时，l = r + 1，nums[l] 表示的 arr 的左侧边界元素，如果不存在的话，返回的大于 target 的最小索引
        // 越界判断
        if (l < 0 || l >= arr.length) {
            return -1;
        }

        return arr[l] == target ? l : l - 1;
    }

}

0 赞同 0 条回复

陆狗陆狗普通 2024年12月9日下午11:24

解题思路
– 第一个大于或者最后一个等于，是相邻的。第一个大于的index-1=最后一个等于的index
– 最后一个小于或第一个等于，是相邻的。最后一个小于的index+1=第一个等于的index
【题解1】

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 3, 4, 5, 5, 7};
        int target = 4;
        int index = upper(arr, target);
        System.out.println(index);

        index = floor_upper(arr, target);
        System.out.println(index);

        index = lower(arr, target);
        System.out.println(index);

        index = floor_lower(arr, target);
        System.out.println(index);

    }

    // 寻找第一个大于 target 的元素的下标
    public static int upper(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        // 判断一下极限值就可以在while循环的时候不去考虑这些极限值了
        // 【错误点】等于也不行
        if (target >= arr[arr.length - 1]) {
            return -1;
        }
        int l = 0;
        int h = arr.length - 1;
        // 循环结束的条件是l==h
        while (l < h) {
            // 【错误点】二分查找的mid的求法，是(h-l)/2，不是(l+h)/2
            int mid = l + (h - l) / 2;
            if (arr[mid] > target) {
                h = mid;
            } else if (arr[mid] == target) {
                l = mid + 1;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    // 如果数组中存在元素等于 target，则返回最后一个等于target 的元素下标，如果不存在，则返回第一个大于 target 的元素下标
    public static int floor_upper(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        if (target > arr[arr.length - 1]) {
            return -1;
        }
        int l = 0;
        int h = arr.length - 1;
        while (l < h) {
            int mid = l + (h - l) / 2;
            if (arr[mid] > target) {
                h = mid;
            } else if (arr[mid] == target) {
                l = mid + 1;
            } else {
                l = mid + 1;
            }
        }
        // 在upper方法的基础上，判断前面一个节点是否和target相等（期间在判断一下界限值）
        if (l - 1 >= 0 && arr[l - 1] == target) {
            return l - 1;
        }
        return l;
    }

    // 寻找最后一个小于 target 的元素的下标
    public static int lower(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        //  【错误点】等于也不行
        if (target <= arr[0]) {
            return -1;
        }
        int l = 0;
        int h = arr.length - 1;
        while (l < h) {
            // 【错误点】int mid = l + (h - l) / 2，当l=3，h=4时，mid=3，导致l=mind，h一直不变
            // 难点：因为l=mid，如果计算出来的mid是l + (h - l) / 2，那么很有可能mid=l，下限一直不能移动
            int mid = l + (h - l + 1) / 2;
            if (arr[mid] > target) {
                h = mid - 1;
            } else if (arr[mid] == target) {
                h = mid - 1;
            } else {
                l = mid;
            }
        }
        return l;
    }

    // 如果数组中存在元素等于 target，则返回第一个等于target 的下标，如果不存在，则返回最后一个小于 target 的元素的下标
    public static int floor_lower(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        if (target < arr[0]) {
            return -1;
        }
        int l = 0;
        int h = arr.length - 1;
        while (l < h) {
            int mid = l + (h - l + 1) / 2;
            if (arr[mid] > target) {
                h = mid - 1;
            } else if (arr[mid] == target) {
                h = mid - 1;
            } else {
                l = mid;
            }
        }
        // 在lower方法的基础上，判断前面一个节点是否和target相等（期间在判断一下界限值）
        if (l + 1 <= arr.length - 1 && arr[l + 1] == target) {
            return l + 1;
        }
        return l;
    }
}

0 赞同 0 条回复

Renasc 普通 2024年12月8日上午11:44

package BinarySearch;

public class SearchModel {
    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);
        System.out.println("index = " + index + ", value = " + arr[index]);  // index = 5, value = 4
        index = floorUpper(arr, target);
        System.out.println("index = " + index + ", value = " + arr[index]);  // index = 4, value = 3
        index = lower(arr, target);
        System.out.println("index = " + index + ", value = " + arr[index]);  // index = 1, value = 2
        index = floorLower(arr, target);
        System.out.println("index = " + index + ", value = " + arr[index]);  // index = 2, value = 3
    }

    // 1. 寻找第一个大于target的元素的下标
    public static int upper(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        int result = -1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] > target) {
                result = mid;
                right = mid - 1;  // 向左寻找
            } else {
                left = mid + 1;   // 向右寻找
            }
        }
        return result;
    }

    // 2. 如果数组中存在元素等于target，则返回最后一个等于target的元素下标，如果不存在，则返回第一个大于target的元素下标
    public static int floorUpper(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        int result = -1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] == target) {
                result = mid;
                left = mid + 1;  // 向右查找
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {  // arr[mid] > target
                result = mid;
                right = mid - 1;
            }
        }
        if (result >= 1 && arr[result - 1] == target) {
            result = result - 1;
        }
        return result;
    }

    // 3. 寻找最后一个小于target元素的下标
    public static int lower(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        int result = -1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] < target) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }

    // 4. 如果数组中存在元素等于target，则返回第一个等于target的下标；如果不存在，则返回最后一个小于target元素的下标
    public static int floorLower(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        int result = -1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] == target) {
                result = mid;
                right = mid - 1;    // 向左查找
            } else if (arr[mid] > target) {
                right = mid - 1;
            } else { // arr[mid] < target
                result = mid;
                left = mid + 1;
            }
        }
        // 判断特殊情况
        if (result < arr.length - 2 && arr[result + 1] == target) {
            result = result + 1;
        }
        return result;
    }
}

0 赞同 0 条回复

lQl 永久会员 2024年12月6日上午12:12

int upper(int[] arr, int target){
    int left = 0, right = arr.length - 1;
    int result = -1;

    while(left <= right){
        int mid = left + (right - left)/2;
        if(arr[mid] > target){
            result = mid;
            right = mid - 1;//向左寻找
        }else {
            left = mid + 1;//向右寻找
        }
    }
    return result;

}

int floor_upper(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    int result = -1;

    while(left <= right) {
        int mid = left + (right - left)/2;
        if(arr[mid] == target){
            result = mid;
            left = mid + 1;//向右寻找
        }else if(arr[mid] < target){
            left = mid + 1;
        }else{
            result = mid;
            right = mid - 1;
        }
    }

    if(result >= 1 && arr[result - 1] == target)
        return result - 1;
    return result;
}

int lower(int[] arr,int target) {
    int left = 0; right = arr.length - 1;
    int result = -1;

    while(left <= right){
        int mid = left + (right - left)/2;
        if(arr[mid] < target){
            result = mid;
            left = mid + 1;//向右寻找
        }else{
            right = mid -1;//向左寻找
        }
    }
    return result;
}

int floor_lower(int[] arr,int target) {
    int left = 0; right = arr.length - 1;
    int result = -1;

    while(left <= right){
        int mid = left + (right - left)/2;
        if(arr[mid]==target){
            result=mid;
            right= mid-1;//向左找
        }else if(arr[mid] < target){
            result = mid;
            left = mid + 1;//向右寻找
        }else{
            right = mid -1;//向左寻找
        }
    }
    if(result < arr.length -2&&arr[result+1]==target)
        return result+1;
    return result;
}

0 赞同 0 条回复

Xiang. 永久会员 2024年12月5日下午9:40

//采用划分蓝红数组颜色边界的思想
//假设数组为[1,2,3,5,5,5,8,9] traget=5
//当查找第一个大于等于target的元素的位置时，此时target为第一个红色的位置，返回right
// 1  2   3  5   5  5  8  9
//蓝 蓝 蓝 红 红 红 红 红

    public int searchRangeFirst(int[] nums, int target){
        int left=-1;
        int right=nums.length;
        int mid=0;
        while(left+1!=right){
            mid=((right-left)/2)+left;   //防止越界
            if(nums[mid]<target) left=mid;
            else right=mid;  //合并了大于或等于两种情况。 
        }
        return right;
    }

//当查找最后一个等于target的元素的位置时，此时target为最后一个蓝色的位置，返回left
// 1  2   3  5   5  5  8  9
//蓝 蓝 蓝 蓝 蓝 蓝 红 红
    public int searchRangeLast(int[] nums, int target){
            int left=-1;
            int right=nums.length;
            int mid=0;
            while(left+1!=right){
                mid=((right-left)/2)+left;   //防止越界
                if(nums[mid]<=target) left=mid;//合并了小于或等于两种情况。
                else  right=mid; 
            }
            return left;
        }
//当查找第一个大于target的元素的位置时，此时target为最后一个蓝色的位置，返回right
// 1  2   3  5   5  5  8  9
//蓝 蓝 蓝 蓝 蓝 蓝 红 红
public int searchRangeLastFirstB(int[] nums, int target){
        int left=-1;
        int right=nums.length;
        int mid=0;
        while(left+1!=right){
            mid=((right-left)/2)+left;   //防止越界
            if(nums[mid]<=target) left=mid;//合并了小于或等于两种情况。
            else  right=mid; 
        }
        return right;
    }
//当查找最后一个小于target的元素的位置时，此时target为第一个红色的位置，返回left
// 1  2   3  5   5  5  8  9
//蓝 蓝 蓝 红 红 红 红 红
public int searchRangeFirstLastL(int[] nums, int target){
        int left=-1;
        int right=nums.length;
        int mid=0;
        while(left+1!=right){
            mid=((right-left)/2)+left;   //防止越界
            if(nums[mid]<target) left=mid;
            else right=mid;  //合并了大于或等于两种情况。 
        }
        return left;
    }

0 赞同 0 条回复

晓宇普通 2024年12月5日下午9:17

#include <vector>
#include <iostream>
using namespace std;
// 确定搜索范围，并不断缩小
// 判断特殊情况
// 1.寻找第一个大于 target 的元素的下标
int upper(vector<int> arr, int target){
    int l = 0, r = arr.size() - 1, mid;
    if(target >= arr[r]) return -1;     //如果都不存在，则返回-1
    while(l < r){
        mid = (r - l) / 2 + l;
        if(arr[mid] > target){
            r = mid;
        }else if(arr[mid] == target){
            l = mid + 1;
        }else{
            l = mid + 1;
        }
    }
    return l;
}

// 2.如果数组中存在元素等于 target，则返回最后一个等于target 的元素下标，如果不存在，则返回第一个大于 target 的元素下标 cout 4
int floor_upper(vector<int> arr, int target){
    int l = 0, r = arr.size() - 1,mid;
    if(target > arr[r]) return -1;//如果都不存在，则返回-1
    while(l < r){
        mid = (r - l) / 2 + l;  // 整数除2向下取整， 所以 r 一定比mid小

        if(arr[mid] > target){
            r = mid;
        }else if(arr[mid] == target){
            l = mid + 1;
        }else{
            l = mid + 1;
        }
    }

    if(l - 1 >= 0 && arr[l - 1] == target){
        return l - 1;
    }

    return l;
}

// 3.寻找最后一个小于 target 的元素的下标  cout 1
int lower(vector<int> arr, int target){
    int l = 0, r = arr.size() - 1,mid;
    if(target  <= arr[l]) return -1;//如果都不存在，则返回-1
    while(l < r){
        mid = (r - l + 1) / 2 + l; // 需要向上取整，故 + 1
        if(arr[mid] > target){
            // [l, mid, r]
            r = mid - 1;
        }else if(arr[mid] == target){ // arr[mid] < mid
            r = mid - 1;
        }else{
            l = mid;
        }

    }

    return l;
}


// 4.如果数组中存在元素等于 target，则返回第一个等于target 的下标，如果不存在，则返回最后一个小于 target 的元素的下标。 cout 2
int floor_lower(vector<int> arr, int target){
    int l = 0, r = arr.size() - 1, mid;
    if(target < arr[l]) return -1;//如果都不存在，则返回-1
    while(l < r){
        mid = (r - l + 1) / 2 + l;
        if(arr[mid] > target){ // [l,mid,r]
            r = mid - 1;
        }else if(arr[mid] == target){
            r = mid - 1;
        }else{
            l = mid;  // arr[l] < target
        }
    }
    if(l + 1 < arr.size() && arr[l + 1] == target) return l + 1;
    return l;
}

int main(void){
    vector<int> arr = {1,2,3,3,3,4,5,5,7};
    int target = 3;
    cout << upper(arr,target) << endl;
    cout << floor_upper(arr,target) << endl;
    cout << lower(arr,target) << endl;
    cout << floor_lower(arr,target) << endl;
    return 0;
}

0 赞同 0 条回复

Kisara 普通 2024年12月5日下午8:59

看了讲解之后独立写的，虽然和讲解一模一样哈哈哈

public class Solution {

    //arr = [1，2，3，3，3，4，5，5，7]，target = 3，那么
    //
    //1.寻找第一个大于 target 的元素的下标，本案例中4 就是第一个大于 target 的元素 ，下标 = 5。
    //对应方法名格式为
    //int upper(int[] arr, int target){
    //
    ////如果都不存在，则返回-1

    int upper(int[] arr, int target){
        int l=0;
        int r=arr.length-1;
        if(arr[r]<target)
            return -1;

        while(l<r){
            int mid=(r-l)/2+1;
            if(arr[mid]>target)
            {
                r=mid;
            }else if(arr[mid]==target)
            {
                l=mid+1;
            }else {
                l=mid+1;
            }
        }
        return l;
    }


    //2.如果数组中存在元素等于 target，则返回最后一个等于target 的元素下标，如果不存在，则返回第一个大于 target 的元素下标。本案例中最后一个等于target的下标 = 4。
    //对应方法名
    //int floor_upper(int[] arr, int target){
    ////如果都不存在，则返回-1
    int floor_upper(int[] arr, int target){
        int l=0;
        int r=arr.length-1;
        if(arr[r]<target) return -1;

        while(l<r){
            int mid=(r-l)/2+1;
            if(arr[mid]>target)
            {
                r=mid;
            }
            else if(arr[mid]==target){
                l=mid+1;
            }else {
                l=mid+1;
            }
        }
        if(l-1>=0&&arr[l-1]==target)
            return l-1;
        else return l;
    }



    //3.寻找最后一个小于 target 的元素的下标，本案例中 2 则是最后一个小于 target 的，下标 = 1.
    //对应方法名格式为
    //int lower(int[] arr, int target){
    //
    ////如果都不存在，则返回-1
    int lower(int[] arr, int target){
        int l=0;
        int r=arr.length-1;
        if(arr[l]>target) return -1;

        while(l<r){
            int mid=(r-l)/2+1;
            if(arr[mid]<target){
                l=mid;
            }else if(arr[mid]==target){
                r=mid-1;
            }else r=mid-1;
        }

        return l;
    }




    //4.如果数组中存在元素等于 target，则返回第一个等于target 的下标，如果不存在，则返回最后一个小于 target 的元素的下标。本案例中第一个等于target的下标 = 2。
    //对应方法名格式为
    //int floor_lower(int[] arr, int target){
    //
    ////如果都不存在，则返回-1
    int floor_lower(int[] arr, int target){
        int l=0;
        int r=arr.length-1;
        if(arr[l]>target) return -1;

        while(l<r){
            int mid=(r-l+1)/2+1;
            if(arr[mid]>target)
                r=mid-1;
            else if(arr[mid]==target)
                r=mid-1;
            else l=mid;
        }
        if(l+1< arr.length&&arr[l+1]==target) return l+1;
        else return l;
    }

}

0 赞同 0 条回复

jaron 普通 2024年12月5日下午6:00

参考讲解写的

//1.寻找第一个大于 target 的元素的下标
public static int upper(int[] arr, int target){
    int l = 0;
    int r = arr.length - 1;
    if(arr[r] <= target){
        return -1;
    }
    while(l < r){
        int mid = (r - l) / 2 + l;
        if(arr[mid] > target){
            //[l ,mid, r]
            r = mid;
        } else if(arr[mid] == target){
            l = mid + 1;
        }else {//arr[mid] < target
            l = mid + 1;
        }
    }
    return l;
}

//2.寻找最后一个等于target 的元素下标，如果不存在，则返回第一个大于 target 的元素下标
public static int floor_upper(int[] arr, int target){
    int l = 0;
    int r = arr.length - 1;
    if(arr[r] < target){
        return -1;
    }
    while(l < r){
        int mid = (r - l) / 2 + l;
        if(arr[mid] > target){
            //[l ,mid, r]
            r = mid;
        } else if(arr[mid] == target){
            l = mid + 1;
        }else {//arr[mid] < target
            l = mid + 1;
        }
    }

    if(l - 1 >= 0 && arr[l - 1] == target){
        return l -1;
    }

    return l;
}

//3.寻找最后一个小于 target 的元素的下标
public  static int lower(int[] arr, int target){
    int l = 0;
    int r = arr.length - 1;
    if(arr[l] >= target){
        return -1;
    }
    while(l < r){
        // r = 1,l = 0,mid = 0
        int mid = (r - l + 1) / 2 + l;
        if(arr[mid] > target){
            //[l ,mid, r]
            r = mid - 1;
        } else if(arr[mid] == target){
            r = mid - 1;
        }else {//arr[mid] < target
            l = mid;
        }
    }
    //
    return l;
}

// 4.寻找第一个等于target 的下标，如果不存在，则返回最后一个小于 target 的元素的下标
public static int floor_lower(int[] arr, int target){
    int l = 0;
    int r = arr.length - 1;
    if(arr[l] > target){
        return -1;
    }
    while(l < r){
        // r = 1,l = 0,mid = 0
        int mid = (r - l + 1) / 2 + l;
        if(arr[mid] > target){
            //[l ,mid, r]
            r = mid - 1;
        } else if(arr[mid] == target){
            r = mid - 1;
        }else {//arr[mid] < target
            l = mid;
        }
    }
    //
    if(l + 1 < arr.length && arr[l + 1] == target){
        return l + 1;
    }
    return l;
}

0 赞同 0 条回复

Aatorx 永久会员 2024年12月5日下午3:10

//返回第一个大于target的目标。
int upper(vector& v, int target) {
    int l = 0;
    int r = v.size()-1;
    if (v[r] <= target) {
        return -1;
    }
    while (l target) {
            r = mid;
        }
    }
    return l;
}

//寻找最后一个等于target的目标，若不存在，则返回第一个大于target的目标。
int floor_upper(vector<int>& v, int target) {
    int l = 0;
    int r = v.size() - 1;
    if (v[r] < target) {
        return -1;
    }
    while (l < r) {
        int mid = (r - l) / 2 + l;
        if (v[mid] > target) {
            r = mid;
        }
        else if (v[mid] == target) {
            l = mid + 1;
        }
        else if (v[mid] < target) {
            l = mid + 1;
        }
    }
    if (l - 1 >= 0 && v[l - 1] == target) {
        return l - 1;
    }
    return l;
}

//寻找最后一个小于target的目标
int lower(vector<int>& v, int target) {
    int l = 0;
    int r = v.size() - 1;
    if (v[l] >= target) {
        return -1;
    }
    while (l < r) {
        int mid = (r - l) / 2 + l;
        if (v[mid] > target) {
            r = mid - 1;
        }
        else if (v[mid] == target) {
            r = mid - 1;
        }
        else if (v[mid] < target) {
            l = mid;
        }
    }
    return l;
}

//返回第一个等于target的目标，若不存在，则返回第一个小于target的目标。
int floor_lower(vector<int>& v, int target) {
    int l = 0;
    int r = v.size() - 1;
    if (v[l] >= target) {
        return -1;
    }
    while (l < r) {
        int mid = (r - l) / 2 + l;
        if (v[mid] > target) {
            r = mid - 1;
        }
        else if (v[mid] == target) {
            r = mid - 1;
        }
        else if (v[mid] < target) {
            l = mid;
        }
    }
    if (l+1 < v.size() && v[l + 1] == target) {
        return l + 1;
    }
    return l;
}

时间复杂度O(logN)，空间复杂度O(N)。

0 赞同 0 条回复

月下足迹普通 2024年12月5日上午10:50

// 1. 寻找第一个大于 target 的元素的下标
public static int upper(int[] arr, int target) {
int left = 0, right = arr.length – 1;
int result = -1;

    while (left <= right) {
        int mid = (right + left) / 2;
        if (arr[mid] > target) {
            result = mid; // 记录可能的结果
            right = mid - 1; // 继续向左搜索
        } else {
            left = mid + 1;
        }
    }
    return result;
}

// 2. 如果存在 target，返回最后一个等于 target 的下标；如果不存在，返回第一个大于 target 的下标
public static int floor_upper(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    int result = -1;
    while (left <= right) {
        int mid = (right + left) / 2;
        if (arr[mid] <= target) {
            if (arr[mid] == target) {
                result = mid; // 更新结果为最后一个等于 target 的下标
            }
            left = mid + 1; // 继续向右搜索
        } else {
            right = mid - 1;
        }
    }
    return result != -1 ? result : upper(arr, target); // 如果不存在 target，则寻找第一个大于 target 的下标
}

// 3. 寻找最后一个小于 target 的元素的下标
public static int lower(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    int result = -1;
    while (left <= right) {
        int mid = (right + left) / 2;
        if (arr[mid] < target) {
            result = mid; // 记录可能的结果
            left = mid + 1; // 继续向右搜索
        } else {
            right = mid - 1;
        }
    }
    return result;
}

// 4. 如果存在 target，返回第一个等于 target 的下标；如果不存在，返回最后一个小于 target 的下标
public static int floor_lower(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    int result = -1;
    while (left <= right) {
        int mid = (right + left) / 2;
        if (arr[mid] >= target) {
            if (arr[mid] == target) {
                result = mid; // 更新结果为第一个等于 target 的下标
            }
            right = mid - 1; // 继续向左搜索
        } else {
            left = mid + 1;
        }
    }
    return result != -1 ? result : lower(arr, target); // 如果不存在 target，则寻找最后一个小于 target 的下标
}

0 赞同 0 条回复

迢迢星野普通 2024年12月4日下午10:19

// 1. 寻找第一个大于 target 的元素的下标：求 target 的右侧边界（如果存在，返回值 + 1，如果不存在，返回值也 + 1）
public int upper(int[] arr, int target) {
    int l = 0, r = arr.length - 1;
    // 判断特殊情况
    if(arr[r] <= target){
        return -1;
    }
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] < target) {
            l = mid + 1;
        }else if (arr[mid] > target) {
            r = mid - 1;
        }else {
            // 求的是右侧边界，收缩左侧边界
            l = mid + 1;
        }
    }
    // 此时，l = r + 1，nums[l - 1] 表示的 arr 的右侧边界，如果不存在的话，返回的小于 target 的最大索引
    // 越界判断
    if (l - 1 < 0 || l - 1 >= arr.length) {
        return -1;
    }
    return l;
}

// 2. 如果数组中存在元素等于 target，则返回最后一个等于 target 的元素下标，如果不存在，则返回第一个大于 target 的元素下标。
public int floor_upper(int[] arr, int target){
    int l = 0, r = arr.length - 1;
    // 判断特殊情况
    if(arr[r] <= target){
        return -1;
    }
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] < target) {
            l = mid + 1;
        }else if (arr[mid] > target) {
            r = mid - 1;
        }else {
            // 求的是右侧边界，收缩左侧边界
            l = mid + 1;
        }
    }
    // 此时，l = r + 1，nums[l - 1] 表示的 arr 的右侧边界元素，如果不存在的话，返回的小于 target 的最大索引
    // 越界判断
    if (l - 1 < 0 || l - 1 >= arr.length) {
        return -1;
    }

    return arr[l - 1] == target ? l - 1 : l;
}

// 3.寻找最后一个小于 target 的元素的下标：寻找 target 的左侧边界，如果存在的话，返回的是 target 的左侧边界（ 结果-1 即可）；
// 如果不存在的话，返回的是大于 target 的最小索引。（结果-1）
public int lower(int[] arr, int target) {
    int l = 0, r = arr.length - 1;

    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] < target) {
            l = mid + 1;
        }else if (arr[mid] > target) {
            r = mid - 1;
        }else {
            // 求的是左侧边界，收缩右侧边界
            r = mid - 1;
        }
    }
    // 此时，l = r + 1，nums[l] 表示的 arr 的左侧边界元素，如果不存在的话，返回的大于 target 的最小索引
    // 越界判断
    if (l < 0 || l >= arr.length) {
        return -1;
    }

    return l - 1;
}


// 4.如果数组中存在元素等于 target，则返回第一个等于 target 的下标，如果不存在，则返回最后一个小于 target 的元素的下标。
public int floor_lower(int[] arr, int target) {
    int l = 0, r = arr.length - 1;

    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] < target) {
            l = mid + 1;
        }else if (arr[mid] > target) {
            r = mid - 1;
        }else {
            // 求的是左侧边界，收缩右侧边界
            r = mid - 1;
        }
    }
    // 此时，l = r + 1，nums[l] 表示的 arr 的左侧边界元素，如果不存在的话，返回的大于 target 的最小索引
    // 越界判断
    if (l < 0 || l >= arr.length) {
        return -1;
    }

    return arr[l] == target ? l : l - 1;
}

时间复杂度：O(logn)
空间复杂度：O(1)

0 赞同 0 条回复

苯庸普通 2024年12月4日下午8:47

public class BinarySearch {
public static void main(String[] args) {
int[] arr = {1,2,3,3,3,4,5,5,7};
int target = 3;
floor_upper(arr, target);
}

// 寻找第一个大于 target 的元素的下标
static void upper(int[] arr, int target){
    int l = 0, r = arr.length-1;
    while(l < r){
        int m = (l + r) / 2;
        if(arr[m] <= target){
            l = m + 1;
        }else{
            r = m;
        }
    }
    System.out.println(l + "_" + r + "_" + arr[l]);
}

// 寻找最后一个小于 target 的元素的下标
static void lower(int[] arr, int target){
    int l = 0, r = arr.length-1;
    while(l < r){
        int m = (l + r) / 2;
        if(arr[m] >= target){
            r = m -1;
        }else{
            l = m;
        }
    }
    System.out.println(l + "_" + r + "_" + arr[l]);
}

// 如果数组中存在元素等于 target，则返回最后一个等于target 的元素下标，如果不存在，则返回第一个大于 target 的元素下标
static void floor_upper(int[] arr, int target){
    int l = 0, r = arr.length-1;
    while(l < r){
        int m = (l + r) / 2;
        if(arr[m] > target){
            r = m;
        }else{
            l = m + 1;
        }
    }
    if(l >= 1 && arr[l-1] == target){
        System.out.println((l-1) + "_" + (r-1) + "_" + arr[l]);
    }else{
        System.out.println(l);
    }

}



// 如果数组中存在元素等于 target，则返回第一个等于target 的下标，如果不存在，则返回最后一个小于 target 的元素的下标
static void floor_lower(int[] arr, int target){
    int l = 0, r = arr.length-1;
    while(l < r){
        int m = (l + r) / 2;
        if(arr[m] < target){
            l = m + 1;
        }else{
            r = m;
        }
    }
    if(l+1 < arr.length && arr[l+1] == target){
        System.out.println((l+1) + "_" + (r+1) + "_" + arr[l]);
    }else{
        System.out.println(l);
    }
}

}
时间：O（lgn）
空间：O（1）

0 赞同 0 条回复

# 回答此问题取消回复

后才能回答

【二分查找专题】给出四种二分查找的模板

答案来了，具体答案看这篇文章：4种二分查找模版讲解

共以下 13 个回答

# 回答此问题 取消回复

# 回答此问题取消回复