九号球普通 2023年11月19日下午10:32

“`java
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; }

0 赞同 0 条回复

怀瑾永久会员 2023年7月18日上午1:37

C++实现

“`C++
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 = l + (r - l)/2; if (arr[mid] > target){
r = mid;
} else if (arr[mid] == target){
l = mid + 1;
} else {
l = mid + 1;
}
}
return l;
}
“`

0 赞同 0 条回复

断舍离永久会员 2023年7月17日下午5:03

/*
    * 返回大于target的最小值索引
    * */
    public static <E extends Comparable<E>> int upper(E[] data, E target){
        int l = 0, r = data.length;
        while (l < r){
            int mid = l + (r-l)/2;
            if(data[mid].compareTo(target) <= 0){
                l = mid + 1;
            }else {
                r = mid;
            }
        }
        //此时l == r
        return l;
    }

    /*
     * ＞target：返回＞target最小值索引
     * 或
     * ==target：返回==target最大索引
     * */
    public static <E extends Comparable<E>> int upper_floor(E[] data, E target){
        int upper = upper(data, target);
        if(upper - 1 >= 0 && data[upper - 1].compareTo(target) == 0){
            return upper - 1;
        }
        return upper;
    }

    /*
     * 返回小于target的最大值索引
     * */
    public static <E extends Comparable<E>> int lower(E[] data, E target){
        int l = 0, r = data.length;
        while (l < r){
            int mid = l + (r-l)/2;
            if(data[mid].compareTo(target) >= 0){
                l = mid - 1;
            }else {
                r = mid;
            }
        }
        //此时l == r
        return l;
    }

    /*
     * <target：返回<target最大值索引
     * 或
     * ==target：返回==target最大索引
     * */
    public static <E extends Comparable<E>> int lower_floor(E[] data, E target){
        int lower = lower(data, target);
        if(lower + 1 < data.length && data[lower + 1].compareTo(target) == 0){
            return lower + 1;
        }
        return lower;
    }

0 赞同 0 条回复

Sexypig. 普通 2023年7月12日下午11:07

本质上都是不断缩小左右范围，操作的不同主要体现在arr[mid]target上：

#include <iostream>
using namespace std;
#include <vector>

// 二分查找,数组有序
// 1.寻找第一个大于 target 的元素的下标,不存在返回-1
int upper(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    // 特殊情况
    if (arr[right] <= target) return -1;
    // 迭代法
    // 此模板为找到最后一个target的下一个元素
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) {
            left = mid + 1;
        } else if (arr[mid] > target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

// 2.如果数组中存在元素等于
// target，则返回最后一个等于target的元素下标，如果不存在，则返回第一个大于
// target 的元素下标。
int floor_upper(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    // 迭代法
    // 该模板和上一模板本质类似，都是找到target然后再进行操作
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) {
            left = mid + 1;
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {  // 重点都在于arr[mid] == target时的操作
            int res = right;
            while (res > mid) {
                if (arr[res] == target) return res;
                --res;
            }
            return mid;
        }
    }
    return left ? left < arr.size() : -1;
}
// 3.寻找最后一个小于 target 的元素的下标
// 如果都不存在，则返回-1
int lower(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) {
            left = mid;
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {
            right = mid - 1;
        }
    }
    return left;
}
// 4.如果数组中存在元素等于 target，则返回第一个等于target
// 的下标，如果不存在，则返回最后一个小于 target 的元素的下标。
// 如果都不存在，则返回-1
int floor_lower(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    if (arr[left] > target) return -1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) {
            left = mid;
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {
            right = mid - 1;
        }
    }
    if (left + 1 < arr.size() && arr[left + 1] == target) return left + 1;
    return left;
}

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

0 赞同 0 条回复

BOZ 普通 2023年7月12日下午2:30

【思路】-
【复杂度】时间O(logn)，空间O(1)

class Solution {
    // arr = [1, 2, 3, 3, 3, 4, 5, 5, 7], target = 3
public:
    int upper(int arr[], int len, int target){
        // if not exist, return -1
        if (arr[len - 1] <= target) return -1;

        // TODO: 寻找第一个大于 target 的元素的下标, 本案例中4 就是第一个大于 target 的元素
        int l = 0, r = len - 1;
        while (l < r) {
            int mid = (r - l) / 2 + l;
            if (arr[mid] <= target) l = mid + 1;
            else if (arr[mid] > target) r = mid;
        }
        return l;
    }

    int floor_upper(int arr[], int len, int target){
        // if not exist, return -1
        if (arr[len - 1] < target) return -1;

        // TODO: 如果数组中存在元素等于 target, 则返回最后一个等于target 的元素下标, 如果不存在, 则返回第一个大于 target 的元素下标。
        int idx = upper(arr, len, target);
        if (idx && arr[idx - 1] == target) return idx - 1;
        else return idx;
    }

    int lower(int arr[], int len, int target){
        // if not exist, return -1
        if (arr[0] >= target) return -1;

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

    int floor_lower(int arr[], int len, int target){
        // if not exist, return -1
        if (arr[0] > target) return -1;

        // TODO: 如果数组中存在元素等于 target, 则返回第一个等于target 的下标, 如果不存在, 则返回最后一个小于 target 的元素的下标。
        int idx = lower(arr, len, target);
        if (idx < len - 1 && arr[idx + 1] == target) return idx + 1;
        else return idx;
    }
};

void test(int arr[], int len, int target) {
    Solution s;
    printf("[upper]: %d\n", s.upper(arr, len, target));
    printf("[floor_upper]: %d\n", s.floor_upper(arr, len, target));
    printf("[lower]: %d\n", s.lower(arr, len, target));
    printf("[floor_lower]: %d\n", s.floor_lower(arr, len, target));
}

int main() {
    int arr[] = {1, 2, 3, 3, 3, 4, 5, 5, 7};
    test(arr, 9, 3);
    return 0;
}

0 赞同 0 条回复

憨憨永久会员 2023年7月12日下午12:31

二分法模板

public class erFen01 {
    public static void main(String[] args) {
        int[] arr={1,2,3,3,3,4,5,7};
        System.out.println(upper(arr,3));
        System.out.println(floor_upper(arr,3));
        System.out.println(lower(arr,3));
        System.out.println(floor_lower(arr,3));
    }
    public static int upper(int[] arr,int target){
        int left=0;
        int right=arr.length-1;
        if(arr[right]<target){
            return -1;
        }
        while(left<right){
            int mid=(right-left)/2+left;
            if(arr[mid]>target){
                right=mid;
            }else{
                left=mid+1;
            }
        }
        return left;
    }
    public static int floor_upper(int[] arr, int target){
        int left = 0;
        int right = arr.length-1;
        if(arr[right] < target){
            return -1;
        }

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

        return left;
    }
    public static int lower(int[] arr, int target){
        int left=0;
        int right=arr.length-1;
        if(arr[right]<target)return -1;

        while(left<right){
            //[l , mid , r]
            int 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;
    }
    public static int floor_lower(int[] arr, int target){
        int left = 0;
        int right = arr.length - 1;
        if(arr[0]>target)return -1;

        while(left<right){
            int 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;
        }else{
            return left;
        }
    }
}

0 赞同 0 条回复

橙子陈普通 2023年7月9日下午11:19

二分法模板
1.寻找第一个大于 target 的元素的下标
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 = l + (r - l)/2;
        if (arr[mid] > target){
           r = mid;
        } else if (arr[mid] == target){
           l = mid + 1;
        } else {
           l = mid + 1;
        }
   }
   return l;
}

2.如果数组中存在元素等于 target，则返回最后一个等于target 的元素下标，如果不存在，则返回第一个大于 target 的元素下标。
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 = l + (r - l)/2;
        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 的元素的下标
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 = l + (r - l + 1)/2;
        if (arr[mid] > target){
           r = mid - 1;
        } else if (arr[mid] == target){
           r = mid - 1;
        } else {
           l = mid;
        }
   }
   return l;
}

4.如果数组中存在元素等于 target，则返回第一个等于target 的下标，如果不存在，则返回最后一个小于 target 的元素的下标。
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 = l + (r - l+ 1)/2;
        if (arr[mid] > target){
           r = mid - 1;
        } else if (arr[mid] == target){
           r = mid - 1;
        } else {
           l = mid;
        }
   }

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

   return l;
}

0 赞同 0 条回复

残月冷骄阳普通 2023年7月9日上午10:36

package org.example;

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

}

//第一种二分查找
public static int greater(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    if (arr[right] <= target) {
        return -1;
    }
    while (left < right) {
        int mid = (right + left) / 2;
        if (arr[mid] > target) {
            right = mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else if (arr[mid] == target) {
            left = mid + 1;
        }
    }
    return left;
}

//寻找第最后一个等于target的数字或者第一个大于target的数字
public static int lastEqualOrGreater(int[] arr, int target) {
    int index = greater(arr, target);
    if (index - 1 > 0 && arr[index - 1] == target) {
        return index - 1;
    } else {
        return index;
    }
}

//寻找最后一个比target小的数字下标；
public static int lastLess(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    if (arr[left] > target) {
        return 0;
    }
    while (left < right) {
        int mid = (left + right) / 2;
        if (arr[mid] > target) {
            right = mid - 1;
        } else if (arr[mid] < target) {
            left = mid;
        } else if (arr[mid] == target) {
            right = mid - 1;
        }
    }
    return left;
}

//寻找最后一个比target小的数字下标或者第一个等于target的下标。
public static int lastLessOrEqual(int[] arr, int target) {
    int index = lastLess(arr, target);
    if (index + 1 > 0 && index + 1 < arr.length && arr[index + 1] == target) {
        return index + 1;
    } else {
        return index;
    }
}

}

0 赞同 0 条回复

mpweixin用户普通 2023年7月9日上午10:33

java
public class Solution {
    //不断缩小搜索范围
    //寻找第一个大于 target 的元素的下标
    public int upper(int[] arr, int target) {
        if(arr[arr.length - 1] <= target ) {
            return -1;
        }
        int left = 0;
        int right = arr.length - 1;
        while(left < right) {
            mid = (left + right) / 2;
            if(arr[mid] > target) {
                right = mid;     //right不能等于mid - 1
            } else if(arr[mid] == target) {
                left = mid + 1;
            } else { //arr[mid] < target
                left = mid + 1;//left = mid 也行
            }
        }
        return left;
    }

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

        //上述功能已经完成了寻找第一个大于target的元素.当前元素减1
        if(left - 1 >= 0 && arr[left - 1] == target){
            return left - 1;
        }

        return l;
    }

    //寻找最后一个小于 target 的元素的下标
    public int lower(int[] arr, int target) {
        if(arr[0] >= target ) {
            return -1;
        }
        int left = 0;
        int right = arr.length - 1;
        while(left < right) {
            mid = (left - right + 1)/2 + left;
            if(arr[mid] > target) {
                right = mid - 1;  //注意这三条语句和第一种模板之间的区别   
            } else if(arr[mid] == target) {
                right = mid - 1;
            } else { //arr[mid] < target
                left = mid;//注意注意，l=0,r=1时,mid = 0会一直持续，循环出不来，要向上取整
            }
        }
        return left;
    }

    //如果数组中存在元素等于 target，则返回第一个等于target 的下标，如果不存在，则返回最后一个小于 target 的元素的下标
    public int floor_int(int[] arr, int target) {
        if(arr[0] >= target ) {
            return -1;
        }
        int left = 0;
        int right = arr.length - 1;
        while(left < right) {
            mid = (left + right) / 2;
            if(arr[mid] > target) {
                right = mid - 1;  //注意这三条语句和第一种模板之间的区别   
            } else if(arr[mid] == target) {
                right = mid - 1;
            } else { //arr[mid] < target
                left = mid;//left = mid 也行
            }
        }

        if(left + 1 <= arr.length && arr[left + 1] == target) {
            return left + 1;
        }
        return left;
    }
}

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

0 赞同 0 条回复

WhyNot 普通 2023年7月7日下午12:06

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

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

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

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

0 赞同 0 条回复

屠龙手段普通 2023年7月7日上午11:32

int upper(vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
    if (arr[right] <= target) return -1;
    while (left < right) {
        // mid向下取整才能不漏元素
        int mid = (right - left) / 2 + left;
        // left = mid + 1 最终收束在target的第一顺位
        if (arr[mid] == target) left = mid + 1;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid;
    }
    return left;
}

int floor_upper(vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
    if (arr[right] <= target) return -1;
    while (left < right) {
        int mid = (right - left) / 2 + left;
        if (arr[mid] == target) left = mid + 1;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid;
    }
    // 判断left - 1 >= 0在数组范围内，且arr[left - 1] == target
    return left - 1 >= 0 && arr[left - 1] == target ? left - 1 : left;
}

int lower(vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
    if (arr[left] > target) return -1;
    while (left < right) {
        // mid向上取整
        int mid = (right - left + 1) / 2 + left;
        // right = mid - 1 最终收束在target的前一位
        if (arr[mid] == target) right = mid - 1;
        else if (arr[mid] < target) left = mid;
        else right = mid - 1;
    }
    return right;
}

int floor_lower(vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
    if (arr[left] > target) return -1;
    while (left < right) {
        int mid = (right - left + 1) / 2 + left;
        if (arr[mid] == target) right = mid - 1;
        else if (arr[mid] < target) left = mid;
        else right = mid - 1;
    }
    // 判断没出界
    return right + 1 <= arr.size() - 1 && arr[right + 1] == target ? right + 1 : right;

0 赞同 0 条回复

局外人普通 2023年7月6日上午8:26

思路：控制边界细节

class test{
    public static int upper(int[] arr, int target){
        int low = 0, high = arr.length - 1;

        if(arr[high]<=target)   return -1;

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

        return low;
    }

    public static int floor_upper(int[] arr, int target){
        int low = 0, high = arr.length-1;

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

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

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

        return low;
    }

    public static int lower(int[] arr, int target){
        int low = 0, high = arr.length-1;

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

        while(low<high){
            int mid = low + (high-low)/2;

            if(arr[mid]<target){
                low = mid;
            }else if(arr[mid]>target){
                high = mid - 1;
            }else if(arr[mid]==target){
                high = mid - 1;
            }
        }

        return low;
    }

    public static int floor_lower(int[] arr, int target){
        int low = 0, high = arr.length - 1;

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

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

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

0 赞同 0 条回复

Ming 普通 2023年7月5日上午10:14

1.寻找第一个大于target的下标，往右寻找 l = mid + 1
2.寻找最后一个等于target的下标，是第一个大的前一个
3.寻找最后一个小于target的下标，往左寻找r = mid – 1
4.寻找第一个等于target的下标，根据小于的下标 + 1

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 条回复

哈哈哈哈开开心心普通 2023年7月4日下午10:42

4种二分查找

def upper(arr, target):
    l, r = 0, len(arr) - 1
    if (arr[r] <= target):
        return -1

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

    return l

def floor_upper(arr, target):
    l, r = 0, len(arr) - 1
    if (arr[r] < target):
        return -1

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

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

    return l


def lower(arr, target):
    l, r = 0, len(arr) - 1
    if (arr[l] >= target):
        return -1

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

    return l


def floor_lower(arr, target):
    l, r = 0, len(arr) - 1
    if (arr[l] >= target):
        return -1

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

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

    return l

0 赞同 0 条回复

名字什么的好麻烦普通 2023年7月4日下午8:49

二分查找

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

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

0 赞同 0 条回复

张开怀普通 2023年7月4日上午10:30

// 1、寻找第一个大于 target 的元素下标
       int search1(vector<int>& nums, int target){
              int left = 0, right = nums.size() - 1;
              if(nums[right] <= target){
                     return -1;
              }
              while(left < right){
                     int mid = (right - left) / 2 + left;
                      if(arr[mid] > target){
                             right = mid;
                      }else{
                             left = mid +1;
                      }
              }
              return left;
       }

// 2、若数组中存在元素等于，则返回最后一个等于target的元素下标
       int search2(vector<int>& nums, int target){
              int left = 0;
              int right = nums.size()-1;
              if(nums[right] < target){
                     return -1;
              }
              while(left<right){
                     int mid = (right - left)/2 +left;
                     if(nums[mid] > target){
                            right = mid;
                     }else{
                            left = mid +1 ;
                     }  
              }
                     if( left - 1>=0 && nums[left -1] == target){
                            return left - 1;
                     }
                     return left;
       }

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

// 4、若数组中存在元素等于target，则返回第一个等于target的下标
       int search4(vector<int>& nums, int target){
              int left = 0;
              int right = nums.size() - 1;
              if(nums[left] > target){.
                     return -1;
              }
              while(left < right){
                     int mid =(right - left + 1) / 2 +1;
                     if(nums[mid] < target){
                            left = mid;
                     }else{
                            right = mid-1;
                     }
              }
              if(left+1 < nums.size() && nums[left + 1] == target){
                     return left +1;
              }
              return left;
       }

0 赞同 0 条回复

伏月三十普通 2023年7月3日下午9:32

public class BanarySort {

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

        int index3 = floor_lower(arr, target);
        System.out.println("index3 = "+ index3);

    }

    //1.寻找第一个大于 target 的元素的下标，案例：arr[1,2,3,3,3,4,5,5,7], target = 3。下标=5
    //最右边的元素加1 如果target不存在 返回-1
    public 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){
                left=mid+1;
            } else if (arr[mid] > target){
                right=mid-1;
            } else if (arr[mid] < target) {
                left=mid+1;
            }
        }
        //如果是8 没有 -1
        if (right>=arr.length-1){
            return -1;
        }
        //单独判断一下
        if(right<=0){
            return 0;
        }
        return right+1;
    }

    //2.如果数组中存在元素等于 target，则返回最后一个等于target 的元素下标，
    // 如果不存在，则返回第一个大于 target 的元素下标
    // 如果都不存在，则返回-1 越界了 返回-1
    //案例：arr[1,2,3,3,3,4,5,5,7], target = 3
    public 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){
                left=mid+1;
            } else if (arr[mid] > target) {
                right=mid-1;
            } else if (arr[mid] < target) {
                left=mid+1;
            }
        }
        if(right>=arr.length-1){
            return -1;
        }
        //单独判断一下
        if(right<=0){
            return 0;
        }
        return arr[right]==target?right:right+1;
    }

    //3.寻找最后一个小于 target 的元素的下标
    // [1,2,3,3,3,4,5,5,7],target = 3;
    //返回的是最左边前面的那个  下标为1
    //如果都不存在 返回-1  target不存在就返回-1
    public  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 if (arr[mid] > target) {
                right=mid-1;
            } else if (arr[mid] < target) {
                left=mid+1;
            }
        }
        if(left<0){
            return -1;
        }
        if(left>=arr.length){
            return left-1;
        }
        return left-1;
    }

    // 4.如果数组中存在元素等于 target，则返回第一个等于target 的下标，
    // 如果不存在，则返回最后一个小于 target 的元素的下标
    //[1,2,3,3,3,4,5,5,7],target = 3; 索引是2
    //返回的是最左边的那个
    public 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 if (arr[mid] > target) {
                right=mid-1;
            } else if (arr[mid] < target) {
                left=mid+1;
            }
        }
        if(left<0){
            return -1;
        }
        if(left>=arr.length){
            return left-1;
        }
        return arr[left]==target?left:left-1;
    }
}

感觉题目要求奇奇怪怪的，很难读懂

0 赞同 0 条回复

花老爷普通 2023年7月3日下午4:49

帅地才是yyds

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

    private 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) / 2;
            if (arr[mid] <= target) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }

    private 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) / 2;
            if (arr[mid] <= target) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        if (l - 1 >= 0 && arr[l - 1] == target) {
            return l - 1;
        }
        return l;
    }

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

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

0 赞同 0 条回复

Dsjh 普通 2023年7月3日下午3:52

MY

b站up五点七边的二分查找

#include <bits/stdc++.h>
using namespace std;
// 返回第一个大于tar的元素下标，没有返回-1
int upper(vector<int>& v,int tar){
    int l=-1,r=v.size();
    // 左区域 <= tar ,右区域 > tar;
    while(l+1!=r){
        int mid = l+(r-l)/2;
        if(v[mid]<=tar) l=mid;
        else r=mid;
    }
    // 没有大于 tar 的，那么左边界在最后
    if(l == v.size()-1){
        return -1;
    }
    return r;
}
// 如果数组中存在元素等于 target，则返回最后一个等于target 的元素下标，
// 如果不存在，则返回第一个大于 target 的元素下标
int floor_upper(vector<int>& v,int tar){
    int l=-1,r=v.size();
    // 左区域 <= tar ,右区域 > tar;
    while(l+1 != r){
        int mid = l+(r-l)/2;
        if(v[mid]<=tar) l=mid;
        else r=mid;
    }
    if(v[l] == tar){
        return l;
    }
    else{
        return r;
    }
}
// 寻找最后一个小于 target 的元素的下标
int lower(vector<int>& v,int tar){
    int l=-1,r=v.size();
    // 左区域 <tar ,右区域 >= tar;
    while(l+1!=r){
        int mid = l+(r-l)/2;
        if(v[mid]<tar) l=mid;
        else r=mid;
    }
    // 没有小于 tar 的，那么右边界在0
    if(r == 0){
        return -1;
    }
    return l;
}
// 如果数组中存在元素等于 target，则返回第一个等于target 的下标，
// 如果不存在，则返回最后一个小于 target 的元素的下标。
int floor_lower(vector<int>& v,int tar){
    int l=-1,r=v.size();
    // 左区域 <tar ,右区域 >= tar;
    while(l+1!=r){
        int mid = l+(r-l)/2;
        if(v[mid]<tar) l=mid;
        else r=mid;
    }
    if(v[r] == tar){
        return r;
    }
    else{
        return l;
    }


}
int main(){
    vector<int> v{1,2,3,3,3,4,5,5,7};
    cout << upper(v,3) << endl;

    cout << floor_upper(v,3) << endl;

    cout << lower(v,3) << endl;

    cout << floor_lower(v,3) << endl;

    return 0;
}

0 赞同 0 条回复

Vow the vow。普通 2023年7月3日上午11:42

要找第一个大于的，就缩小左边界；要找第一个小于的，就缩小右边界。

//寻找第一个大于 target 的元素的下标
    public static int largeFirst(int[] arr, int target){
        int l = 0, r = arr.length-1;
        int bound = -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{
                bound = mid;
                l = mid+1;
            }
        }
        return bound+1;
    }

    //则返回最后一个等于target 的元素下标，如果不存在，则返回第一个大于 target 的元素下标。
    public static int getFirst(int[] arr, int target){
        int l = 0, r = arr.length-1;
        int bound = -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{
                bound = mid;
                l = mid+1;
            }
        }
        if(bound != -1) return  bound;
        return l;
    }

    // 寻找最后一个小于 target 的元素的下标
    public static int lastSmall(int[] arr, int target){
        int l = 0, r = arr.length-1;
        int bound = -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{
                bound = mid;
                r = mid-1;
            }
        }
        return r;
    }

    // 如果数组中存在元素等于 target，则返回第一个等于target 的下标，如果不存在，则返回最后一个小于 target 的元素的下标。
    public static int getLast(int[] arr, int target){
        int l = 0, r = arr.length-1;
        int bound = -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{
                bound = mid;
                r = mid-1;
            }
        }
        if(bound != -1) return bound;
        return r;
    }

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月2日下午9:48

//1.寻找第一个大于 target 的元素的下标
    public static int search(int[] nums, int target) {

        int left = 0;
        int right = nums.length - 1;

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

        return left == nums.length ? -1 : left;
    }

    //2.如果数组中存在元素等于 target，则返回最后一个等于target 的元素下标，
    //如果不存在，则返回第一个大于 target 的元素下标
    public static int search2(int[] nums, int target) {

        int left = 0;
        int right = nums.length - 1;

        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] < target){
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        //判断是否存在target
        if(right != -1 && nums[right] == target){//结束时，如果存在target，right指向最后一个
            //保证right合法，当所有数都大于target时，right等于-1
            return right;
        }
        //不存在target，则返回第一个大于target的元素
        return left == nums.length ? -1 : left;
    }

    //3.寻找最后一个小于 target 的元素的下标
    public static int search3(int[] nums, int target) {

        int left = 0;
        int right = nums.length - 1;

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

        return right == -1 ? -1 : right;
    }

    //4.如果数组中存在元素等于 target，则返回第一个等于target 的下标，
    //如果不存在，则返回最后一个小于 target 的元素的下标。
    public static int search4(int[] nums, int target) {

        int left = 0;
        int right = nums.length - 1;

        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] < target){
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }else {
                right = mid - 1;
            }
        }
        //判断是否存在target
        if(left < nums.length && nums[left] == target){   //结束时，如果存在target，left指向第一个
            //要保证left合法（所有数都比target小时，left指向nums.length，数组越界）
            return left;
        }
        //不存在，返回最后一个小于 target 的元素的下标
        return right == -1 ? -1 : right;
    }

0 赞同 0 条回复

行动派小彩笔普通 2023年7月2日下午8:54

#include<iostream>
#include<vector>
using namespace std;

int upper(vector<int>& nums, int target)
{
    /*
    vector<int> nums{1,2,3,3,3,4,5,5,7 };
    int target = 3;
    */
    int left = 0;
    int right = nums.size() - 1;
    if (nums[right] <= target) return -1; //// 题目要求找一个大于target的元素的下标，不存在返回-1
    // [left,right] 不断搜小范围，直到范围里面只有一个元素，那个就是要查找的
    while (left < right) //当left = right 就退出循环
    {
        int mid = (right - left) / 2 + left;
        if (nums[mid] > target)
        {
            right = mid;
        }
        else if(nums[mid]==target)
        {
            left = mid + 1;
        }
        else //arr[mid]<target;
        {
            left = mid + 1;
        }
    }
 /*   if (left == right)
        cout << "相等" << endl;*/
    return left;
}

int equal_upper(vector<int>& nums, int target)
{
    /*
   vector<int> nums{1,2,3,3,3,4,5,5,7 };
   int target = 3;
   */
    int left = 0;
    int right = nums.size() - 1;
    if (nums[right] < target) return -1;  //查找数组等于target的元素，存在返回下标，不存在返回第一个大于target元素的下标
    while (left < right)
    {
        int mid = (right - left) / 2 + left;
        if (nums[mid] > target)
        {
            right = mid;
        }
        else if (nums[mid] == target)
        {
            left = mid + 1;
        }
        else  //arr[mid]<target;
        {
            left = mid + 1;
        }
    }
    if (left - 1 >= 0 && nums[left - 1] == target)
    {
        return left - 1;
    }
    return left; //第一个大于target的值
}

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

    return left;
}

int equel_lower(vector<int>& nums, int target)
{
    int left = 0;
    int right = nums.size() - 1;
    if (nums[left] > target) return -1;
    while (left < right)
    {
        int mid = (right - left) / 2 + left;
        if (nums[mid] > target)
        {
            right = mid - 1;
        }
        else if(nums[mid]==target)
        {
            right = mid - 1;
        }
        else
        {
            left = mid;
        }
    }
    if (left + 1 <= nums.size() && nums[left + 1] == target)
        return left + 1;
    return left;
}


int main()
{
    int num;
    vector<int> nums{1,2,3,3,3,4,5,5,7 };
    int target = 3;
    // 1. 找一个大于target的元素的下标
    cout << upper(nums, target) << endl;
    // 2.查找数组等于target的元素，存在返回下标，不存在返回第一个大于target元素的下标
    int index2 = equal_upper(nums, target);
    // 3.寻找最后一个小于target的元素的下标
    int index3 = lower(nums, target);
    // 4.查找数组中等于target元素，存在返回下标，不存在返回最后一个小于target元素的下标
    int index4 = equel_lower(nums, target);

    return 0;
}

0 赞同 0 条回复

张君雅小妹妹普通 2023年7月2日下午8:37

看完讲解会了
1. 确定搜索范围
2. 不断缩小范围
3. 判断特殊情况

package leetcode.solution;

public class SolutionBinarySearchTem {
    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 的元素的下标，本案例中4 就是第一个大于 target 的元素 ，下标 = 5。
    static int upper(int[] arr, int target) {
        int l = 0;
        int r = arr.length - 1;
        if(arr[r] <= target) {
            //如果都不存在，则返回-1
            return -1;
        }

        while(l < r){
            int mid = l + ((r - l) >> 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。
    static int floor_upper(int[] arr, int target) {
        int l = 0;
        int r = arr.length - 1;
        if(arr[r] < target) {
            //如果都不存在，则返回-1
            return -1;
        }

        while(l < r){
            int mid = l + ((r - l) >> 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;
        }
        return l;
    }

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

        while(l < r){
            int mid = l + ((r - l + 1) >> 1);  // important!!! 向上取整，为了避免出现l等于mid情况
            if(arr[mid] > target){
                r = mid - 1;
            } else if(arr[mid] == target){
                r = mid - 1;
            } else {
                l = mid;
            }
        }
        return l;
    }

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

    static int floor_lower(int[] arr, int target) {
        int l = 0;
        int r = arr.length - 1;
        if(arr[l] > target) {
            //如果都不存在，则返回-1
            return -1;
        }

        while(l < r){
            int mid = l + ((r - l + 1) >> 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;
        }
        return l;
    }
}

0 赞同 0 条回复

yxy 普通 2023年7月2日下午7:32

给一个常用的二分模板：

int main()
{
    int n,q,x;
    cin>>n>>q;
    for(int i=0;i<n;i++)
        scanf("%d", &a[i]);
    while(q--)
    {
        cin>>x;
        int l=0,r=n-1;
        while(l<r)
        {
            int mid=(l+r)>>1;
            if(a[mid]>=x)
                r=mid;
            else
                l=mid+1;
        }
        if(a[l]==x)
            cout<<l<<" ";
        else
            cout<<"-1 ";

        l=0,r=n-1;
        while(l<r)
        {
            int mid=(l+r+1)>>1;
            if(a[mid]<=x)
                l=mid;
            else
                r=mid-1;
        }
        if(a[l]==x)
            cout<<l<<endl;
        else
            cout<<"-1"<<endl;
    }
    return 0;
}

0 赞同 0 条回复

peach 普通 2023年7月2日下午6:11

1.寻找第一个大于 target 的元素的下标
本案例中4 就是第一个大于 target 的元素，下标 = 5。

int upper(int[] arr, int target){
    int i = 0, j = arr.length - 1;
    if (arr[j] <= target) return -1; //先处理特殊情况
    while(i <= j){
        int m = (i + j) >>> 1;
        if (arr[m] > target){
            j = m - 1;
        }else{
            i = m + 1;
        }
    }
    return i;
}

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

int floor_upper(int[] arr, int target){
    int i = 0, j = arr.length - 1;
    if (arr[j] < target) return -1; //这里先判断一下是个好习惯哈哈
    while (i <= j){
        int m = (i + j) >>> 1;
        if (arr[m] > target){
            j = m - 1;
        }else{
            i = m + 1;
        }
        //到此，i - 1代表≤tar的最右侧元素
        //如果数组中这个位置元素和tar相等，那就找到了，符合要求
        //如果不等，那就返回右侧的元素
    }
    return i - 1 >= 0 && arr[i - 1] == target ? i - 1 : i;
}

3.寻找最后一个小于 target 的元素的下标
本案例中 2 则是最后一个小于 target 的，下标 = 1.

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

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

int floor_lower(int[] arr, int target){
    int i = 0, j = arr.length - 1;
    if (arr[i] > target) return -1;
    while (i <= j){
        int m = (i + j) >>> 1;
        if (arr[m] < target){
            i = m + 1;
        }else{
            j = m - 1;
        }
    }
    return i < arr.length && arr[i] == target ? i : i - 1;
}

0 赞同 0 条回复

Yodl. 普通 2023年7月2日下午2:11

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 条回复

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

共以下 26 个回答

MY

# 回答此问题取消回复

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

共以下 26 个回答

MY

# 回答此问题 取消回复

# 回答此问题取消回复