Gg 普通 2023年3月30日下午11:25

public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = new int[]{7};
        System.out.println(upper(arr, 3));
        System.out.println(lower(arr, 3));
    }

    private static int upper(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] <= target) {
                left = mid + 1;
            } else if (arr[mid] > target) {
                right = mid;
            }
        }
        if (left > 1 && arr[left - 1] == target) {
            return left - 1;
        }
        return -1;
    }

    // 找出第一个等于的值
    private static int lower(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < target) {
                left = mid + 1;
            } else if (arr[mid] >= target) {
                right = mid;
            }
        }
        if (arr[left] == target) {
            return left;
        }
        return -1;
    }
}

0 赞同 0 条回复

lucca 普通 2023年1月7日下午4:01

核心在于把区间分成两个部分，然后判断对于mid取到每种情况，下一步区间应该怎么缩小

    // 第一个大于 target 的下标, 都不存在返回-1
    int upper(int[] arr, int target) {
        int l = 0, r = arr.length - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (arr[mid] > target) r = mid;
            else l = mid + 1;
        }
        return arr[l] > target ? l : -1;
    }

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

    // 最后一个小于 target 的元素的下标, 都不存在返回-1
    int lower(int[] arr, int target) {
        int l = 0, r = arr.length - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (arr[mid] < target) l = mid;
            else r = mid - 1;
        }
        return arr[l] < target ? l : -1;
    }

    // 第一个等于 target 的下标,不存在返回最后一个小于 target 的下标, 都不存在返回-1
    int floor_lower(int[] arr, int target) {
        int l = 0, r = arr.length - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (arr[mid] < target) l = mid + 1;
            else r = mid;
        }

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

0 赞同 0 条回复

PatNick 普通 2023年1月4日上午10:57

arr = [1,2,3,3,3,4,5,5,7]
target = 3

# 1.寻找第一个大于 target 的元素的下标，案例：arr[1, 2,3,3,3,4,5,5,7], target = 3。
def upper(arr,target):
    # 左右两个指针
    l = 0
    r = len(arr) - 1

    if arr[r] <= target:
        return -1

    while(l < r):
        mid = l + (r - l) // 2
        if arr[mid] > target:
            r = mid
        elif arr[mid] == target:
            l = mid + 1
        else:
            l = mid + 1

    return l

#2.如果数组中存在元素等于 target，则返回最后一个等于target 的元素下标，
#如果不存在，则返回第一个大于 target 的元素下标
#案例：arr[1, 2,3,3,3,4,5,5,7], target = 3。
def floor_upper(arr,target):
    l = 0
    r = len(arr) - 1

    if arr[r] < target :
        return -1
    if arr[r] == target:
        return r
    while l < r:
        mid = l + (r - l) // 2
        # 【l,mid,r]
        if arr[mid] > target:
            r = mid
        elif arr[mid] == target:
            l = mid + 1
        else:
            l = mid + 1

    if (l-1) >= 0 and arr[l-1] == target:
        return l-1
    return l


#3.寻找最后一个小于 target 的元素的下标
#[1, 2,3,3,3,4,5,5,7],target = 3;
def lower(arr,target):
    l = 0
    r = len(arr) - 1

    if arr[l] >= target:
        return -1
    while l < r:
        mid = l + (r - l + 1) // 2
        if arr[mid] > target:
            r = mid - 1
        elif arr[mid] == target:
            r = mid - 1
        else:
            l = mid

    return l

#4.如果数组中存在元素等于 target，则返回第一个等于target 的下标，
# 如果不存在，则返回最后一个小于 target 的元素的下标
# [1, 2,3,3,3,4,5,5,7],target = 3;

def floor_lower(arr,target):
    l = 0
    r = len(arr) - 1

    if arr[l] > target:
        return -1
    if arr[l] == target:
        return l

    while l < r:
        # 这里加一是为了向上取整
        # 因为如果r = 1,l = 0,向下取整的话mid = 0，这样如果走到最后的else（l = mid）,这样区间依然为【0，1】并没有缩小，这样就会陷入死循环，所以mid就需要向上取整
        # 但是上面两种情况就不用向上取整，因为在向下取整的情况下，是不可能存在计算出的mid等于r（因为向下取整），所以即使走到r = mid，区间也在缩小，不会死循环
        mid = l + (r - l + 1) // 2
        if arr[mid] > target:
            r = mid - 1
        elif arr[mid] == target:
            r = mid - 1
        else:
            l = mid

    if l+ 1 < len(arr) and arr[l + 1] == target:
        return l + 1
    return l

0 赞同 0 条回复

浅夏的无奈普通 2022年11月30日下午10:22

package sort;

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 = floor_lower(arr, target);
        System.out.println("index = "+ index + ", value = " + arr[index]);

    }

    //1.寻找第一个大于 target 的元素的下标，案例：arr[1, 2,3,3,3,4,5,5,7], target = 3。
    public static int upper(int[] arr, int target){
    // 二分查找需要想清楚的点
        int l = 0;
        int r = arr.length - 1;
        // 判断特殊情况
        if(arr[r] <= target){
            return -1;
        }
        //[l,r],，在我们二分查找的过程中，不断缩小我们的查找范围，直到范围里面只有一个元素，那个就是我们要找的元素了
        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 的元素下标，
    // 如果不存在，则返回第一个大于 target 的元素下标
    //案例：arr[1, 2,3,3,3,4,5,5,7], target = 3。
    public static int floor_upper(int[] arr, int target){
        int l = 0;
        int r = arr.length - 1;
        // 判断特殊情况
        if(arr[r] < target){
            return -1;
        }
        //[l,r],，在我们二分查找的过程中，不断缩小我们的查找范围，直到范围里面只有一个元素，那个就是我们要找的元素了
        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 的元素的下标
    // [1, 2,3,3,3,4,5,5,7],target = 3;
    public  static int lower(int[] arr, int target){
        int l = 0;
        int r = arr.length - 1;
        // 判断特殊情况
        if(arr[l] >= target){
            return -1;
        }
        //[l,r],，在我们二分查找的过程中，不断缩小我们的查找范围，直到范围里面只有一个元素，那个就是我们要找的元素了
        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 的下标，
    // 如果不存在，则返回最后一个小于 target 的元素的下标
    //[1, 2,3,3,3,4,5,5,7],target = 3;
    public static int floor_lower(int[] arr, int target){
        int l = 0;
        int r = arr.length - 1;
        // 判断特殊情况
        if(arr[l] > target){
            return -1;
        }
        //[l,r],，在我们二分查找的过程中，不断缩小我们的查找范围，直到范围里面只有一个元素，那个就是我们要找的元素了
        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 条回复

symbol 普通 2022年11月28日下午6:16

func main() {
    arr := []int{1, 2, 3, 3, 3, 4, 5, 5, 7}
    target := 3
    var res int
    //不断缩小范围，知道范围内只有一个元素
    //1 寻找第一个大于target的元素的下标 返回：index = 5,value = 4
    res = Help_1(arr, target)
    fmt.Println(res)
    fmt.Println(arr[res])

    //2 如果数组中存在元素等于target,则返回最后一个等于target的元素下标
    //如果不存在,则返回第一个大于target的元素下标  返回：index =4, value = 3
    //情况1的变体
    res = Help_2(arr, target)
    fmt.Println(res)
    fmt.Println(arr[res])

    //3 寻找最后一个小于target的元素的下标  返回：index =1, value = 2
    res = Help_3(arr, target)
    fmt.Println(res)
    fmt.Println(arr[res])

    //4 如果数组中存在元素等于target,则返回第一个等于target的下标
    //如果不存在,则返回最后一个小于target的元素的下标 返回：index=2 value=3
    // 情况3的变体
    res = Help_4(arr, target)
    fmt.Println(res)
    fmt.Println(arr[res])

}

// 1 寻找第一个大于target的元素的下标
func Help_1(arr []int, target int) int {
    l := 0
    r := len(arr) - 1
    // 查找范围[l, r]
    ///特殊情况: 寻找的是第一个大于target的元素下标，
    //数组是有序的，如果数组都最后一个元素小于等于target的话，则不存在这样的元素
    if arr[r] <= target {
        return -1
    }
    for l < r {
        mid := (r-l)/2 + l // 向下取整 r不会等于 mid,不会造成死循环
        if arr[mid] > target {
            // [l, mid, r] 找的是第一个大于target的元素的下标,所以范围所消息为：[1, mid]
            //右边界能取mid,是因为寻找的是第一个待遇target的元素的下标,而arr[mid] > target
            //则mid是有可能取到的
            r = mid
        } else if arr[mid] == target {
            // 找的是第一个大于target的元素下标 如果arr[mid] == target的话，
            // 第一个大于target的元素 范围应该在[mid+1, r]
            // 左边界取mid + 1,是因为寻找的是第一个大于taeget的元素的下标,
            // 而arr[mid] == target,mid是不可能取到的,而mid+1是有可能取到的
            l = mid + 1
        } else { //arr[mid] < target
            // [l, mid, r]   [mid+1, r]
            // 左边界取mid + 1,是因为寻找的是第一个大于taeget的元素的下标,
            // 而arr[mid] < target,mid是不可能取到的,而mid+1是有可能取到的
            l = mid + 1
        }
    }
    return l // 最后l和r会相等
}

//2 如果数组中存在元素等于target,则返回最后一个等于target的元素下标
//如果不存在,则返回第一个大于target的元素下标
func Help_2(arr []int, target int) int {
    l := 0
    r := len(arr) - 1
    //特殊情况: 寻找的是最后一个等于target的元素下标
    //数组是有序的，若数组的最后一个元素都小于target的话，则数组汇中不存在target
    if arr[r] < target {
        return -1
    }
    for l < r {
        mid := (r-l)/2 + l // 向下取整 r不会等于 mid,不会造成死循环
        if arr[mid] > target {
            // [l, mid, r] 找的是第一个大于target的元素的下标,所以范围所消息为：[1, mid]
            //右边界能取mid,是因为寻找的是第一个待遇target的元素的下标,而arr[mid] > target
            //则mid是有可能取到的
            r = mid
        } else if arr[mid] == target {
            // 找的是第一个大于target的元素下标 如果arr[mid] == target的话，
            // 第一个大于target的元素 范围应该在[mid+1, r]
            // 左边界取mid + 1,是因为寻找的是第一个大于taeget的元素的下标,
            // 而arr[mid] == target,mid是不可能取到的,而mid+1是有可能取到的
            l = mid + 1
        } else { //arr[mid] < target
            // [l, mid, r]   [mid+1, r]
            // 左边界取mid + 1,是因为寻找的是第一个大于taeget的元素的下标,
            // 而arr[mid] < target,mid是不可能取到的,而mid+1是有可能取到的
            l = mid + 1
        }
    }
    // 上面for循环找的是第一个大于target的元素下标
    //若果上面的下标-1 == target,则下标-1是所求的最后一个等于target的元素下标
    //若不等于target,则返回下标
    if l-1 >= 0 && arr[l-1] == target {
        return l - 1
    }
    return l
}

//3 寻找最后一个小于target的元素的下标
func Help_3(arr []int, target int) int {
    l := 0
    r := len(arr) - 1
    // 特殊情况：若最左边的元素都大于等于target的话,则不存在寻找的下标
    if arr[l] >= target {
        return -1
    }
    for l < r {
        // mid := (r-l)/2 + l 向下取整 l可能会等于 mid,不会缩小范围,造成死循环 因此 需要调整
        mid := (r-l+1)/2 + l //向上取整
        if arr[mid] > target {
            //[l, mid, r] 找到是最后一个小于target的元素的下标,范围缩小为：[l, mid-1]
            //右边界取mid-1,是因为求的是最后一个小于target的元素的下标,
            // 而arr[mid] > target,不可能取值mid,但有可能取mid-1
            r = mid - 1
        } else if arr[mid] == target {
            // 找到是最后一个小于target的元素的下标，范围缩小为：[l, mid-1]
            //右边界取mid-1,是因为求的是最后一个小于target的元素的下标,
            // 而arr[mid] == target,不可能取值mid,但有可能取mid-1
            r = mid - 1
        } else { // arr[mid] < target
            //找的是最后一个小于target的元素的下标，范围缩小为：[mid, r]
            //左边界能取mid,是因为求的是最后一个小于target的元素的下标，
            //而 arr[mid] < trget,mid有可能是所求下标
            l = mid
        }
    }
    return l // 最后l和r会相等
}

//4 如果数组中存在元素等于target,则返回第一个等于target的下标
//如果不存在,则返回最后一个小于target的元素的下标
func Help_4(arr []int, target int) int {
    l := 0
    r := len(arr) - 1
    // 特殊情况：若最左边的元素都大于target的话,则不存在寻找的下标
    if arr[l] > target {
        return -1
    }
    for l < r {
        // mid := (r-l)/2 + l 向下取整 l可能会等于 mid,不会缩小范围,造成死循环 因此 需要调整
        mid := (r-l+1)/2 + l //向上取整
        if arr[mid] > target {
            //[l, mid, r] 找到是最后一个小于target的元素的下标,范围缩小为：[l, mid-1]
            //右边界取mid-1,是因为求的是最后一个小于target的元素的下标,
            // 而arr[mid] > target,不可能取值mid,但有可能取mid-1
            r = mid - 1
        } else if arr[mid] == target {
            // 找到是最后一个小于target的元素的下标，范围缩小为：[l, mid-1]
            //右边界取mid-1,是因为求的是最后一个小于target的元素的下标,
            // 而arr[mid] == target,不可能取值mid,但有可能取mid-1
            r = mid - 1
        } else { // arr[mid] < target
            //找的是最后一个小于target的元素的下标，范围缩小为：[mid, r]
            //左边界能取mid,是因为求的是最后一个小于target的元素的下标，
            //而 arr[mid] < trget,mid有可能是所求下标
            l = mid
        }
    }
    //上面for循环找的是最后一个小于target的元素的下标
    //若果上面的下标+1 == target,则下标+1是所求的第一个等于target的元素下标
    //若不等于target,则返回下标
    if l+1 < len(arr) && arr[l+1] == target {
        return l + 1
    }
    return l // 最后l和r会相等
}

0 赞同 0 条回复

天然普通 2022年11月21日下午10:37

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

    }
    //1.寻找第一个大于 target 的元素的下标，本案例中4 就是第一个大于 target 的元素 ，下标 = 5。
    public static int upper(int[] arr,int target){
        int left = 0;
        int right = arr.length-1;
        while (left < right){
            int mid = left+(right-left+1)/2;
            if (arr[mid] > target){
                right = mid-1;
            }else{
                left = mid;
            }
        }
        if(arr[left] != target) return -1;
        if (left == arr.length-1 && arr[left] == target) return -1;
        return left+1;
    }
    //2.如果数组中存在元素等于 target，则返回最后一个等于target 的元素下标，如果不存在，则返回第一个大于 target 的元素下标。本案例中最后一个等于target的下标 = 4。
    public static int  floor_upper(int[] arr,int target){
        int left = 0;
        int right = arr.length - 1;
        while (left < right){
            int mid = left+(right-left+1)/2;
            if (arr[mid] > target){
                right = mid-1;
            }else{
                left = mid;
            }
        }
        if(arr[left] != target) return -1;
        return left;
    }
    //3.寻找最后一个小于 target 的元素的下标，本案例中 2 则是最后一个小于 target 的，下标 = 1.
    public static int lower(int[] arr,int target){
        int left = 0;
        int right = arr.length - 1;
        while (left < right){
            int mid = left+(right-left)/2;
            if (arr[mid]>=target){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        if(arr[left] != target) return -1;
        if (left == 0 && arr[left] == target) return -1;
        return left-1;
    }
    //4.如果数组中存在元素等于 target，则返回第一个等于target 的下标，如果不存在，则返回最后一个小于 target 的元素的下标。本案例中第一个等于target的下标 = 2。
    public static int floor_lower(int[] arr,int target){
        int left = 0;
        int right = arr.length - 1;
        while (left < right){
            int mid = left+(right-left)/2;
            if (arr[mid]>=target){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        if(arr[left] != target) return -1;
        return left;
    }
}

0 赞同 0 条回复

yanshuojune 普通 2022年11月19日上午11:47

def upper(arr, target):
    # 返回大于target的第一个元素的下标
    L, R = 0, len(arr) - 1
    # 判断目标元素不在列表范围内的情况
    if arr[R] < target or arr[L] > target:
        return -1
    while L <= R:
        mid = (R - L) // 2 + L
        # target在左半边
        if arr[mid] > target:
            R = mid - 1
        # target在右半边
        else:
            L = mid + 1
    return L

def floor_upper(nums, taget):
    L, R = 0, len(nums) - 1
    if arr[R] < target or arr[L] > target:
        return -1
    while L <= R:
        mid  = L + (R - L) // 2
        if nums[mid] > target:
            R = mid - 1
        elif nums[mid] < target:
            L = mid + 1
        else:
            L = mid + 1
    if nums[L - 1] == target and L - 1 >= 0:
        return L - 1
    return L

def lower(nums, target):
    '''
    寻找最后一个小于target的元素的下标
    思路：寻找第一个等于target的元素，前一个元素就是最后一个小于target元素的下标'''
    L, R = 0, len(nums) - 1
    if nums[L] > target or nums[R] < target:
        return -1
    while L < R:
        mid = L + (R - L + 1) // 2 # 向上取整
        if nums[mid] > target:
            R = mid - 1
        elif nums[mid] < target:
            L = mid
        else:
            R = mid - 1
    return L

def floor_lower(nums, target):
    L, R = 0, len(nums) - 1
    if nums[L] > target or nums[R] < target:
        return -1
    while L <= R:
        mid = L + (R - L) // 2
        if nums[mid] > target:
            R = mid - 1
        elif nums[mid] < target:
            L = mid + 1
        else:
            R = mid - 1
    if nums[L] != target and L -1 >= 0:
        return L - 1
    return L

0 赞同 0 条回复

y 普通 2022年11月14日下午10:35

  // 1.寻找第一个大于 target 的元素的下标，本案例中4 
就是第一个大于 target 的元素 ，下标 = 5。
    function upper(arr, target) {
      let l = 0;
      let r = arr.length - 1;
      if (arr[r] < target) return -1;
      while (l <= r) {
        let mid = Math.floor((r + l) / 2);
        if (arr[mid] > target) {
          r = mid - 1;
        } else if (arr[mid] === target) {
          l = mid + 1;
        } else {
          l = mid + 1;
        }
      }
      return l;
    }

    // 2.如果数组中存在元素等于 
target，则返回最后一个等于target 的元素下标，
    // 如果不存在，则返回第一个大于 target 的元素下标。
    // 本案例中最后一个等于target的下标 = 4。
    function floor_upper(arr, target) {
      let l = 0;
      let r = arr.length - 1;
      if (arr[r] < target) return -1;
      while (l <= r) {
        let mid = Math.floor((r + l) / 2);
        if (arr[mid] > target) {
          r = mid - 1;
        } 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 的元素的下标，

    // 本案例中 2 则是最后一个小于 target 的，下标 = 1.

    function lower(arr, target) {
      let l = 0;
      let r = arr.length - 1;
      if (arr[r] < target) return -1;
      while (l <= r) {
        let mid = Math.floor((r + l) / 2);
        if (arr[mid] > target) {
          r = mid - 1;
        } else if (arr[mid] === target) {
          r = mid - 1;
        } else {
          l = mid + 1;
        }
      }
      return l - 1;
    }

    // 4.如果数组中存在元素等于 
target，则返回第一个等于target 的下标，
    // 如果不存在，则返回最后一个小于 target 
的元素的下标。本案例中第一个等于target的下标 = 2。

    function floor_lower(arr, target) {
      let l = 0;
      let r = arr.length - 1;
      if (arr[r] < target) return -1;
      while (l <= r) {
        let mid = Math.floor((r + l) / 2);
        if (arr[mid] > target) {
          r = mid - 1;
        } else if (arr[mid] === target) {
          r = mid - 1;
        } else {
          l = mid + 1;
        }
      }
      if (l - 1 < arr.length && arr[l - 1] === target) {
        return l - 1;
      }
      return l ;
    }

0 赞同 0 条回复

訁訁訁訁訁普通 2022年11月13日下午8:02

/**
 * @author ty
 * @create 2022-11-05 21:44
 */

/**
 * 二分查找需要xi
 */
public class BinarySearch {
    //arr = [1, 2, 3, 3, 3, 4, 5, 5, 7] target = 3
    //1.寻找第一个大于 target 的元素的下标，
    // 本案例中4 就是第一个大于 target 的元素 ，下标 = 5。
    public static int upper(int[] arr, int target) {
        //二分查找需要想清楚的点
        int l = 0;
        int r = arr.length - 1;//[l,r] 在二分查找过程中不断缩小查找范围，直到范围里只有一个元素，就是要查找的元素
        //先判断特殊情况
        if (arr[r] <= target) {
            return -1;
        }
        while (l < r) {//l == r退出循环
            int mid = (r - l) / 2 + l;
            if (arr[mid] > target) {
                //[l,mid]
                r = mid;
            } else if (arr[mid] == target) {
                l = mid + 1;
            } else if (arr[mid] < target) {
                l = mid + 1;
            }
        }
        return l;
    }

    //2.如果数组中存在元素等于 target，则返回最后一个等于target 的元素下标，
    // 如果不存在，则返回第一个大于 target 的元素下标。
    // 本案例中最后一个等于target的下标 = 4。
    //如果都不存在，则返回-1
    public static int floor_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;
            if (arr[mid] > target) {
                r = mid;//mid 一定比r小
            } else if (arr[mid] == target) {
                l = mid + 1;
            } else if (arr[mid] < target) {
                l = mid + 1;
            }
        }
        if(l - 1 >= 0 && arr[l - 1] == target){
            return l - 1;
        }
        return l;
    }

    //3.寻找最后一个小于 target 的元素的下标，
    // 本案例中 2 则是最后一个小于 target 的，下标 = 1.
    //都不存在返回-1
    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) {
            int mid = (r - l + 1) / 2 + l;//需要向上取整
            if (arr[mid] > target) {
                r = mid - 1;
            } else if (arr[mid] == target) {
                r = mid - 1;
            } else if (arr[mid] < target) {
                l = mid;//如果 r = 1 l = 0 则 mid = 0，区间没有收缩 需要向上取整
            }
        }
        return l;
    }

    //4.如果数组中存在元素等于 target，则返回第一个等于target 的下标，
    // 如果不存在，则返回最后一个小于 target 的元素的下标。
    // 本案例中第一个等于target的下标 = 2。
    //如果都不存在返回-1
    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) {
            int mid = (r - l + 1) / 2 + l;//需要向上取整
            if (arr[mid] > target) {
                r = mid - 1;
            } else if (arr[mid] == target) {
                r = mid - 1;
            } else if (arr[mid] < target) {
                l = mid;//如果 r = 1 l = 0 则 mid = 0，区间没有收缩 需要向上取整
            }
        }
        if(l + 1 < arr.length && arr[l + 1] == target){
            return  l + 1;
        }
        return l;
    }

    public static void main(String[] args) {
        BinarySearch binarySearch = new BinarySearch();
        int[] arr = new int[]{1, 2, 3, 3, 3, 4, 5, 5, 7};
        int index = binarySearch.floor_lower(arr, 5);
        System.out.println("index = " + index + ",value = " + arr[index]);
    }
}

0 赞同 0 条回复

黎昕普通 2022年11月12日下午11:06

——楼上Y7n05h

int upper(const vector<int> &arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        auto tmp = arr[mid];
        if (tmp > target) {
            right = mid - 1;
        } else if (tmp == target) {
            left = mid + 1;
        } else if (tmp < target) {
            left = mid + 1;
        }
    }
    return left == arr.size() ? -1 : left;
}

int floor_upper(const vector<int> &arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        auto tmp = arr[mid];
        if (tmp > target) {
            right = mid - 1;
        } else if (tmp == target) {
            left = mid + 1;
        } else if (tmp < target) {
            left = mid + 1;
        }
    }
    if (left < 1) return 0;
    if (arr[left - 1] == target) return left - 1;
    if (left == arr.size()) return -1;
    return left;
}
int lower(const vector<int> &arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        auto tmp = arr[mid];
        if (tmp > target) {
            right = mid - 1;
        } else if (tmp == target) {
            right = mid - 1;
        } else if (tmp < target) {
            left = mid + 1;
        }
    }
    return right < 0 ? -1 : right;
}
int floor_lower(const vector<int> &arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        auto tmp = arr[mid];
        if (tmp > target) {
            right = mid - 1;
        } else if (tmp == target) {
            right = mid - 1;
        } else if (tmp < target) {
            left = mid + 1;
        }
    }
    assert(right >= -1);
    assert(right + 1 <= arr.size());
    if (right + 1 == arr.size()) return right;
    if (arr[right + 1] == target) return right + 1;
    if (right >= 0) return right;
    return -1;
}

0 赞同 0 条回复

Y7n05h 普通 2022年11月12日上午11:34

int upper(const vector<int> &arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        auto tmp = arr[mid];
        if (tmp > target) {
            right = mid - 1;
        } else if (tmp == target) {
            left = mid + 1;
        } else if (tmp < target) {
            left = mid + 1;
        }
    }
    return left == arr.size() ? -1 : left;
}

int floor_upper(const vector<int> &arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        auto tmp = arr[mid];
        if (tmp > target) {
            right = mid - 1;
        } else if (tmp == target) {
            left = mid + 1;
        } else if (tmp < target) {
            left = mid + 1;
        }
    }
    if (left < 1) return 0;
    if (arr[left - 1] == target) return left - 1;
    if (left == arr.size()) return -1;
    return left;
}
int lower(const vector<int> &arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        auto tmp = arr[mid];
        if (tmp > target) {
            right = mid - 1;
        } else if (tmp == target) {
            right = mid - 1;
        } else if (tmp < target) {
            left = mid + 1;
        }
    }
    return right < 0 ? -1 : right;
}
int floor_lower(const vector<int> &arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        auto tmp = arr[mid];
        if (tmp > target) {
            right = mid - 1;
        } else if (tmp == target) {
            right = mid - 1;
        } else if (tmp < target) {
            left = mid + 1;
        }
    }
    assert(right >= -1);
    assert(right + 1 <= arr.size());
    if (right + 1 == arr.size()) return right;
    if (arr[right + 1] == target) return right + 1;
    if (right >= 0) return right;
    return -1;
}

时间复杂度：O(lgN)

0 赞同 0 条回复

小肸永久会员 2022年11月11日下午8:20

import org.junit.Test;

public class BinarySearch {
    /**
     *
     * @param arr
     * @param target
     * @return 数组中大于target的第一个元素的下标,不存在则返回-1
     */
    public int upper(int[] arr, int target) {
        int len = arr.length;
        int left = 0, right = len - 1;
        // 若数组元素都小于等于target，直接返回-1
        if (arr[right] <= target) {
            return -1;
        }
        while (left < right) {
            int mid = (right - left) / 2 + left;
            if (arr[mid] > target) {
                right = mid;
            } else { //因为arr[mid] == target 和arr[mid] < target两种情况所作操作一样，所以可以合并
                left = mid + 1;
            }
        }
        return left;
    }
    @Test
    public void testUpper() {
        int[] nums = {1, 2, 2, 3, 3, 4, 4, 5, 5};
        System.out.println("预计输出: 5");
        System.out.println("实际输出: " + upper(nums, 3));
    }

    /**
     *
     * @param arr
     * @param target
     * @return target在arr中的最后的一个下标, 否则返回大于target的第一个元素在arr的下标，否则返回-1
     */
    public int floor_upper(int[] arr, int target) {
        int len = arr.length;
        int left = 0, right = len - 1;
        // 若数组元素都小于等于target，直接返回-1
        if (arr[right] < target) {
            return -1;
        }
        while (left < right) {
            int mid = (right - left) / 2 + left;
            if (arr[mid] > target) {
                right = mid;
            } else { //因为arr[mid] == target 和arr[mid] < target两种情况所作操作一样，所以可以合并
                left = mid + 1;
            }
        }
        // 先找到大于target的第一个元素的下标，再判断前一个元素是否等于target决定是否返回target在arr中最后一个下标
        if (left - 1 > 0 && arr[left - 1] == target) {
            return left - 1;
        }
        return left;
    }
    @Test
    public void testFloorUpper() {
        int[] nums = {1, 2, 2, 3, 3, 4, 4, 5, 5};
        System.out.println("预计输出: 4");
        System.out.println("实际输出: " + floor_upper(nums, 3));
    }

    /**
     *
     * @param arr
     * @param target
     * @return arr中最后一个小于target的元素，不存在返回-1
     * */
    public int lower(int[] arr, int target) {
        int len = arr.length;
        int left = 0, right = len - 1;
        if (arr[left] >= target) {
            return -1;
        }
        while (left < right) {
            // 这里向上取整, 防止left==mid，导致搜索范围不会缩小而导致死循环
            int mid = (right - left + 1) / 2 + left;
            if (arr[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return left;
    }
    @Test
    public void testLower() {
        int[] nums = {1, 2, 2, 3, 3, 4, 4, 5, 5};
        System.out.println("预计输出: 2");
        System.out.println("实际输出: " + lower(nums, 3));
    }

    /**
     *
     * @param arr
     * @param target
     * @return 返回target在arr第一次出现的下标，否则返回最后一个小于target的元素下标，否则返回-1
     */
    public int floor_lower(int[] arr, int target) {
        int len = arr.length;
        int left = 0, right = len - 1;
        if (arr[left] > target) {
            return -1;
        }
        while (left < right) {
            // 这里向上取整, 防止left==mid，导致搜索范围不会缩小而导致死循环
            int mid = (right - left + 1) / 2 + left;
            if (arr[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        // 先找到小于target的最后一个元素的下标，再判断后一个元素是否等于target决定是否返回target在arr中第一个下标
        if (left + 1 < len && arr[left + 1] == target) {
            return left + 1;
        }
        return left;
    }
    @Test
    public void testFloorLower() {
        int[] nums = {1, 2, 2, 3, 3, 4, 4, 5, 5};
        System.out.println("预计输出: 3");
        System.out.println("实际输出: " + floor_lower(nums, 3));
    }
}

0 赞同 0 条回复

lobort 普通 2022年11月11日下午5:09

package day03;

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


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

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

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

0 赞同 0 条回复

波波_1936 普通 2022年11月11日下午4:59

    /**
     * 二分查找的模版
     * 1.寻找第一个大于 target 的元素的下标，本案例中4 就是第一个大于 target 的元素 ，下标 = 5。
     */
//    1、
    int upper(int[] arr, int target) {
        if (arr == null || arr.length == 0) return -1;
        int left = 0, right = arr.length - 1, mid = 0;
        if (arr[right] <= target) return -1;
        //缩小范围
        while (left < right) {
            mid = (right - left) / 2 + left;
            if (arr[mid] == target) {
                left = mid + 1;
            } else if (arr[mid] > target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    /**
     * 2.如果数组中存在元素等于 target，则返回最后一个等于target 的元素下标，如果不存在，则返回第一个大于 target 的元素下标。本案例中最后一个等于target的下标 = 4。
     */
    int floor_upper(int[] arr, int target) {
        if (arr == null || arr.length == 0) return -1;
        int left = 0, right = arr.length - 1, mid = 0;
        if (arr[right] < target) return -1;
        //缩小范围
        while (left < right) {
            mid = (right - left) / 2 + left;
            if (arr[mid] == target) {
                left = mid + 1;
            } else if (arr[mid] > target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        if (left - 1 >= 0 && arr[left - 1] == target) {
            return left - 1;
        }
        return left;
    }

    /**
     * 3.寻找最后一个小于 target 的元素的下标，本案例中 2 则是最后一个小于 target 的，下标 = 1.
     */
    int lower(int[] arr, int target) {
        int left = 0, right = arr.length - 1, mid = 0;
        if (arr[left] >= target) return -1;
        //缩小范围
        while (left < right) {
            mid = (right - left + 1) / 2 + left;
            if (arr[mid] == target) {
                right = mid - 1;
            } else if (arr[mid] > target) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return left;
    }

    /**
     * 4.如果数组中存在元素等于 target，则返回第一个等于target 的下标，如果不存在，则返回最后一个小于 target 的元素的下标。本案例中第一个等于target的下标 = 2。
     */
    int floor_lower(int[] arr, int target) {
        int left = 0, right = arr.length - 1, mid = 0;
        if (arr[left] > target) return -1;
        //缩小范围
        while (left < right) {
            mid = (right - left + 1) / 2 + left;
            if (arr[mid] == target) {
                right = mid - 1;
            } else if (arr[mid] > target) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        if (left + 1 < arr.length && arr[left + 1] == target) {
            return left + 1;
        }
        return left;
    }

0 赞同 0 条回复

@ 普通 2022年11月11日上午11:16

6种变种

一.upper（寻找大于target或大于等于target的值）

public class Upper {
    //返回大于 target 的最小索引
    public static 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
                r = mid;

        }

        return l;

    }

    // > target ，返回最小值索引
    // == target，返回最小索引
    public static 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
                r = mid;

        }

        return l;
    }

    // > target ，返回最小值索引
    // == target，返回最大索引
    public static int ceil_upper(int[] arr, int target) {
        int res = upper(arr, target);
        if (res - 1 >= 0 && arr[res - 1] == target)
            return res - 1;
        return res;
    }


    public static void main(String[] args) {

        int[] arr = {1, 1, 3, 3, 5, 5};
        System.out.println(Upper.upper(arr, 3)); // 4
        System.out.println(Upper.floor_upper(arr, 3));// 2
        System.out.println(Upper.ceil_upper(arr, 3));// 3


    }


}

二.lower(寻找小于target 或小于等于target的值)

//注意：对于lower的问题,mid要向上取整 ，即 mid = l + (r - l + 1) / 2，否则会出现死循环
public class Lower {
    //返回小于 target 的最大索引
    public static int lower(int[] arr, int target) {
        int l = 0, r = arr.length - 1;

        if (arr[0] > target)
            return -1;

        while (l < r) {
            int mid = l + (r - l + 1) / 2;

            if (arr[mid] < target)
                l = mid;
            else
                r = mid - 1;

        }

        return l;

    }

    // < target ，返回最大索引
    // == target，返回最大索引
    public static int ceil_lower(int[] arr, int target) {
        int l = 0, r = arr.length - 1;

        if (arr[0] > target)
            return -1;

        while (l < r) {
            int mid = l + (r - l + 1) / 2;

            if (arr[mid] <= target)
                l = mid;
            else
                r = mid - 1;

        }

        return l;

    }

    // < target ，返回最小索引
    // == target，返回最大索引
    public static int floor_lower(int[] arr, int target) {
        int res = lower(arr, target);

        if (res + 1 <= arr.length - 1 && arr[res + 1] == target)
            return res + 1;

        return res;

    }

    public static void main(String[] args) {


        int[] arr = {1, 1, 3, 3, 5, 5};
        System.out.println(Lower.lower(arr, 3)); // 1
        System.out.println(Lower.ceil_lower(arr, 3));// 3
        System.out.println(Lower.floor_lower(arr, 3));// 2
        System.out.println();
    }
}

0 赞同 0 条回复

庄重普通 2022年11月11日上午9:03

//1.寻找第一个大于 target 的元素的下标，案例：arr[1, 2,3,3,3,4,5,5,7], target = 3。
int upper(const vector<int>& arr,const int target){
    // 二分查找需要想清楚的点
    int l = 0;
    int r = arr.size() - 1;
    // 判断特殊情况
    if(arr[r] <= target){
        return -1;
    }
    //[l,r],，在我们二分查找的过程中，不断缩小我们的查找范围，直到范围里面只有一个元素，那个就是我们要找的元素了
    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 的元素下标，
// 如果不存在，则返回第一个大于 target 的元素下标
//案例：arr[1, 2,3,3,3,4,5,5,7], target = 3。
int floor_upper(const vector<int>& arr,const int target){
    int l = 0;
    int r = arr.size() - 1;
    // 判断特殊情况
    if(arr[r] < target){
        return -1;
    }
    //[l,r],，在我们二分查找的过程中，不断缩小我们的查找范围，直到范围里面只有一个元素，那个就是我们要找的元素了
    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 的元素的下标
// [1, 2,3,3,3,4,5,5,7],target = 3;
int lower(const vector<int>& arr,const int target){
    int l = 0;
    int r = arr.size() - 1;
    // 判断特殊情况
    if(arr[l] >= target){
        return -1;
    }
    //[l,r],，在我们二分查找的过程中，不断缩小我们的查找范围，直到范围里面只有一个元素，那个就是我们要找的元素了
    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 的下标，
// 如果不存在，则返回最后一个小于 target 的元素的下标
//[1, 2,3,3,3,4,5,5,7],target = 3;
int floor_lower(const vector<int>& arr,const int target){
    int l = 0;
    int r = arr.size() - 1;
    // 判断特殊情况
    if(arr[l] > target){
        return -1;
    }
    //[l,r],，在我们二分查找的过程中，不断缩小我们的查找范围，直到范围里面只有一个元素，那个就是我们要找的元素了
    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 条回复

西西弗斯的石头永久会员 2022年11月7日下午4:14

根据地哥例题代码自己写了一遍



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

    }
    //1.寻找第一个大于 target 的元素的下标，本案例中4 就是第一个大于 target 的元素 ，下标 = 5。
    public static int upper(int[] arr,int target){
        int left = 0;
        int right = arr.length-1;
        while (left < right){
            int mid = left+(right-left+1)/2;
            if (arr[mid] > target){
                right = mid-1;
            }else{
                left = mid;
            }
        }
        if(arr[left] != target) return -1;
        if (left == arr.length-1 && arr[left] == target) return -1;
        return left+1;
    }
    //2.如果数组中存在元素等于 target，则返回最后一个等于target 的元素下标，如果不存在，则返回第一个大于 target 的元素下标。本案例中最后一个等于target的下标 = 4。
    public static int  floor_upper(int[] arr,int target){
        int left = 0;
        int right = arr.length - 1;
        while (left < right){
            int mid = left+(right-left+1)/2;
            if (arr[mid] > target){
                right = mid-1;
            }else{
                left = mid;
            }
        }
        if(arr[left] != target) return -1;
        return left;
    }
    //3.寻找最后一个小于 target 的元素的下标，本案例中 2 则是最后一个小于 target 的，下标 = 1.
    public static int lower(int[] arr,int target){
        int left = 0;
        int right = arr.length - 1;
        while (left < right){
            int mid = left+(right-left)/2;
            if (arr[mid]>=target){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        if(arr[left] != target) return -1;
        if (left == 0 && arr[left] == target) return -1;
        return left-1;
    }
    //4.如果数组中存在元素等于 target，则返回第一个等于target 的下标，如果不存在，则返回最后一个小于 target 的元素的下标。本案例中第一个等于target的下标 = 2。
    public static int floor_lower(int[] arr,int target){
        int left = 0;
        int right = arr.length - 1;
        while (left < right){
            int mid = left+(right-left)/2;
            if (arr[mid]>=target){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        if(arr[left] != target) return -1;
        return left;
    }
}

```

0 赞同 0 条回复

T 普通 2022年11月7日下午3:52

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

  /**
   * 查找最后一个等于给定值的元素, 如果不存在，则返回第一个大于 target 的元素下标
   */
  public static int floorUpper(int[] arr, int target){
    int low = 0;
    int high = arr.length - 1;
    while(low <= high) {
      int mid = low + ((high - low) >> 1);
      if(arr[mid] > target) {
        if(mid == 0) {
          return mid;
        }
        if(arr[mid - 1] == target) {
          return mid - 1;
        }
        if(arr[mid - 1] < target) {
          return mid;
        }
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    return -1;
  }

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

  /**
   * 如果数组中存在元素等于 target，则返回第一个等于target 的下标
   * 如果不存在，则返回最后一个小于 target 的元素的下标
   */
  static int floorLower(int[] arr, int target){
    int low = 0;
    int high = arr.length - 1;
    while(low <= high) {
      int mid = low + ((high - low) >> 1);
      if(arr[mid] < target) {
        if(mid == arr.length - 1) {
          return mid;
        }
        if(arr[mid + 1] == target) {
          return mid + 1;
        }
        if(arr[mid + 1] > target) {
          return mid;
        }
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
    return -1;
  }
}

0 赞同 0 条回复

你有点可爱喔普通 2022年11月7日下午3:12

package find;

/**
 * @author TangXiaoYang
 * @version 2022.1.3
 * @date 2022/11/5 21:41
 */
public class BinarySearch {

    /**
     * 二分查找：定义查找范围【left,right】,求出查找的中点mid,定义一个数字num[mid],与target数字进行大小的比较
     * 相等：num[mid]==target；返回num[mid];
     * num[mid] < target:返回mid右侧下标,查找范围缩小一半
     * num[mid] > target:返回mid左侧下标因为只能在左边,查找范围缩小一半
     */
    int search(int[] arr, int target) {
        //如果都不存在，则返回-1
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            int num = arr[mid];
            //如果等于目标树则进行返回
            if (num == target) {
                return num;
                //目标数小于中点数字，则在右半边
            } else if (num > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

    /*1.寻找第一个大于 target 的元素的下标，本案例中4 就是第一个大于 target 的元素 ，下标 = 5对应方法名格式为*/
    int upper(int[] arr, int target) {
        //如果都不存在，则返回-1
        int left = 0;
        int right = arr.length - 1;
        int i = 0;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            int num = arr[mid];
            if (target < num) {
                right = mid - 1;
                i = mid;
            } else {
                left = mid + 1;
            }
        }
        if (target < arr[i]) {
            return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        BinarySearch search = new BinarySearch();
        int[] arr = {1, 2, 3, 3, 3, 4, 5, 5, 7};
        int upper = search.upper(arr, 5);
        System.out.println(upper);
        int i = search.floor_upper(arr, 6);
        System.out.println("i = " + i);
        int lower = search.lower(arr, 4);
        System.out.println("lower = " + lower);
        int floor_lower = search.floor_lower(arr, 3);
        System.out.println("floor_lower = " + floor_lower);

    }

    /**
     * 如果数组中存在元素等于 target，则返回最后一个等于target 的元素下标，
     * 如果不存在，则返回第一个大于 target 的元素下标。
     * 本案例中最后一个等于target的下标 = 4。对应方法名
     */
    int floor_upper(int[] arr, int target) {
        //如果都不存在，则返回-1
        int left = 0;
        int right = arr.length - 1;
        int isFalse = -1;
        int i = 0;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (arr[mid] == target) {
                i = mid;
            } else if (arr[mid] > target) {
                right = mid - 1;
                isFalse = mid;
            } else {
                left = mid + 1;
            }
        }
        return isFalse == -1 ? i : isFalse;
    }

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

        }
        if (right < arr.length) {
            return right;
        }
        return isFalse;
    }

    /**
     * 如果数组中存在元素等于 target，则返回第一个等于target 的下标，如果不存在，则返回最后一个小于 target 的元素的下标。
     * 本案例中第一个等于target的下标 = 2。对应方法名格式为
     */
    int floor_lower(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        int isFalse = -1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (arr[mid] >= target) {
                // 由于要求等于target的最小的下标，所以这里移动右边界r，反之则移动左边界l
                isFalse = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return isFalse;
    }
}

0 赞同 0 条回复

cxc 普通 2022年11月6日下午10:05

int upper(int[] arr, int target){//如果都不存在，则返回-1
    int length = arr.length;
        if(arr==null || length < 1) return -1;

        int left = 0;
        int right = length - 1;
        int i = right;
        while(left <= right) {
            int middle = (left+right)/2;
            if(target < arr[middle]) {
                i = middle;
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }

        if (target < arr[i]) return i;
        return -1;
}

int floor_upper(int[] arr, int target){
//如果都不存在，则返回-1
 int length = arr.length;
        if(arr==null || length < 1) return -1;

        int left = 0;
        int right = length - 1;
        int i = right;
        while(left <= right) {
            int middle = (left+right)/2;
            if(target < arr[middle]) {
                i = middle;
                right = middle - 1;
            } else if(target > arr[middle]){
                left = middle + 1;
            } else {
                return middle;
            }
        }

        if (target < arr[i]) return i;
        return -1;
}

int lower(int[] arr, int target){//如果都不存在，则返回-1
 int length = arr.length;
        if(arr==null || length < 1) return -1;

        int left = 0;
        int right = length - 1;
        int i = right;
        while(left <= right) {
            int middle = (left+right)/2;
            if(target < arr[middle]) {
                i = middle;
                right = middle - 1;
            } else if(target > arr[middle]){
                left = middle + 1;
            } else {
                return middle;
            }
        }
    //这里应该取n-1
        if (arr[i-1] < target) return i;
        return -1;
}

int floor_lower(int[] arr, int target){//如果都不存在，则返回-1
 int length = arr.length;
        if(arr==null || length < 1) return -1;

        int left = 0;
        int right = length - 1;
        int i = right;
        while(left <= right) {
            int middle = (left+right)/2;
            if(target < arr[middle]) {
                i = middle;
                right = middle - 1;
            } else if(target > arr[middle]){
                left = middle + 1;
            } else {
                return middle;
            }
        }

        if (arr[i-1] < target) return i;
        return -1;
}

0 赞同 0 条回复

青木普通 2022年11月5日下午10:53

可能有点错误

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

/**
    如果数组中存在元素等于 target，则返回最后一个等于target 的元素下标，
    如果不存在，则返回第一个大于 target 的元素下标。
 */
int floor_upper(int[] arr, int target){
    int l = 0, r = arr.length - 1;
    while(l <= r){
        int mid = l + ((r - l) >> 1);
        if(arr[mid] > target){
            r = mid - 1;
        }
        else{
            l = mid + 1;
        }
    }
    if(l > arr.length-1 && arr[l-1]!=target) return -1;
    return  arr[l-1]==target ? l-1 : l;
}

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

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

0 赞同 0 条回复

派大星普通 2022年11月5日下午7:52

public class Solution1 {
    //1.寻找第一个大于 target 的元素的下标
    int upper(int[] arr, int target){
        if(arr==null || arr.length < 1) return -1;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] > target) return i;
        }
        return -1;
    }
    //2.如果数组中存在元素等于 target，则返回最后一个等于target 的元素下标，如果不存在，则返回第一个大于 target 的元素下标。
    int floor_upper(int[] arr, int target){
        if(arr==null || arr.length < 1) return -1;
        for (int i = arr.length - 1; i >= 0; i--) {
            if(arr[i] == target) return i;
        }
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] > target) return i;
        }
        return -1;
    }
    //3.寻找最后一个小于 target 的元素的下标.
    int lower(int[] arr, int target){
        if(arr==null || arr.length < 1) return -1;
        for (int i = arr.length - 1; i >= 0; i--) {
            if(arr[i] < target) return i;
        }
        return -1;
    }

    //4.如果数组中存在元素等于 target，则返回第一个等于target 的下标，如果不存在，则返回最后一个小于 target 的元素的下标。
    int floor_lower(int[] arr, int target){
        if(arr==null || arr.length < 1) return -1;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] == target) return i;
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            if(arr[i] < target) return i;
        }
        return -1;
    }
}

0 赞同 0 条回复

阿白普通 2022年11月5日下午7:35

class Solution {
public:
    //寻找第一个大于 target 的元素的下标
    int upper(vector<int>& nums, int target) {
        int ans = -1;
        int left = 0;
        int right = nums.size() - 1;

        while (left <= right)
        {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target)
            {
                ans = mid + 1;
                left = mid + 1;
            }
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
        }
        return  ans;
    }

    //.如果数组中存在元素等于 target，则返回最后一个等于target 的元素下标，如果不存在，则返回第一个大于 target 的元素下标
    int floor_upper(vector<int>& nums, int target) {
        int ans = -1;
        int upperPos = 0;
        int left = 0;
        int right = nums.size() - 1;

        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
            {
                ans = mid;
                left = mid + 1;
            }
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
            {
                right = mid - 1;
                upperPos = mid;
            }
        }
        return ans == -1 ? upperPos : ans;
    }

    //寻找最后一个小于 target 的元素的下标
    int lower(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int ans = -1;
        int lPos = -1;
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
            {
                right = mid - 1;
                ans = mid;
            }
            else if (nums[mid] < target)
            {
                left = mid + 1;
                lPos = mid;
            }
            else if (nums[mid] > target)
                right = mid - 1;

        }
        return ans == -1 ? lPos : ans - 1;
    }
    //如果数组中存在元素等于 target，则返回第一个等于target 的下标，如果不存在，则返回最后一个小于 target 的元素的下标
    int floor_lower(vector<int> &nums, int target)
    {
        int left = 0;
        int right = nums.size() - 1;
        int ans = -1;
        int lPos = -1;

        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
            {
                right = mid - 1;
                ans = mid;
            }
            else if (nums[mid] < target)
            {
                left = mid + 1;
                lPos = left;
            }
            else if (nums[mid] > target)
                right = mid - 1;

        }
        return ans == -1 ? lPos : ans;
    }

    //寻找第一个等于 target 的元素的下标
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;

        while (left <= right)
        {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
        }
        return -1;
    }

};

0 赞同 0 条回复

是梦终空永久会员 2022年11月5日下午5:15

寻找第一个大于 target 的元素的下标，本案例中4 就是第一个大于 target 的元素 ，下标 = 5。
    static int upper(int[] arr, int target) {
        int len = arr.length;
        int l = 0;
        int r = len - 1;

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

如果数组中存在元素等于 target，则返回最后一个等于target 的元素下标，如果不存在，则返回第一个大于 target 的元素下标。本案例中最后一个等于target的下标 = 4
    static int floor_upper(int[] arr, int target) {
        int len = arr.length;
        int r = len - 1;
        int l = 0;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (arr[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        if(l>0){
            if(arr[l - 1] == target){
                return l - 1;
            }
        }
        return l<len?   l:-1;
    }

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

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

1 赞同 0 条回复

So 普通 2022年11月5日上午11:49

第13天第一题

public class Solution {
    static int upper(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (arr[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left < arr.length ? left : -1;
    }

    static int floor_upper(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (arr[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        if (left > 0) {
            if (arr[left - 1] == target) {
                return left - 1;
            }
        }
        return left < arr.length ? left : -1;
    }

    static int lower(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (arr[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return right >= 0 ? right : -1;
    }

    static int floor_lower(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (arr[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        if (right < arr.length - 1) {
            if (arr[right + 1] == target) {
                return right + 1;
            }
        }
        return right >= 0 ? right : -1;
    }
}

0 赞同 1 条回复

shuaidi 永久会员 @ So 2022年11月5日下午2:13

容易混淆，自己想个方法区分+1 和2，3 和 4 有相似性，可以进行复用勒。

登录以回复

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

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

共以下 25 个回答

核心在于把区间分成两个部分，然后判断对于mid取到每种情况，下一步区间应该怎么缩小

6种变种

一.upper（寻找大于target或大于等于target的值）

二.lower(寻找小于target 或小于等于target的值)

# 回答此问题取消回复

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

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

共以下 25 个回答

核心在于把区间分成两个部分，然后判断对于mid取到每种情况，下一步区间应该怎么缩小

6种变种

一.upper（寻找大于target或大于等于target的值）

二.lower(寻找小于target 或 小于等于target的值)

# 回答此问题 取消回复

二.lower(寻找小于target 或小于等于target的值)

# 回答此问题取消回复