讨论/《二分查找》 - 在排序数组中查找元素的第一个和最后一个位置/
《二分查找》 - 在排序数组中查找元素的第一个和最后一个位置
共 14 个回复
var searchRange = function(nums, target) {
    var left = 0, right = nums.length - 1;
    while (left + 1 < right) {
        var mid = Math.floor((right - left) / 2) + left;
        if (target < nums[mid]) {
            right = mid;
        } else if (target === nums[mid]) {
            var l = mid, r = mid;
            while (target === nums[--l]) {
                continue
            }
            while (target === nums[++r]) {
                continue
            }
            return [++l, --r];
        } else {
            left = mid;
        }
    }
    if (target === nums[left] && target === nums[right]) return [left, right];
    if (target === nums[left]) return [left, left];
    if (target === nums[right]) return [right, right];
    return [-1, -1];
};
4

bisect_left,bisect_right的写法

def bisect_left(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x: lo = mid + 1
        else: hi = mid
    return lo
def bisect_right(a,x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if x < a[mid]: hi = mid
        else: lo = mid + 1
    return lo
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        start = bisect_left(nums, target)
        if start >= len(nums) or nums[start] != target:
            return [-1, -1]
        return [start, bisect_right(nums, target)-1]
1

呜呜呜写了一上午烂代码
没有测试用例根本就不知道错在哪
好菜啊
截屏2021-04-19 上午10.45.41.png

public int[] searchRange(int[] nums, int target) {
        if(nums.length == 0)
            return new int[]{-1, -1};
        if(nums.length == 1){
            if(nums[0] == target)
                return new int[]{0, 0};
            else
                return new int[]{-1, -1};
        }

        int left = 0, right = nums.length-1;
        int[] res = {-1, -1};

        while (left + 1 < right){
            
            int mid = left + (right - left)/2;
            if(nums[mid] == target){
                int index = mid-1;
                while(index >= 0){
                    if(nums[index] != target){
                        res[0] = index+1;
                        break;
                    }
                    index--;
                }
                if(index == -1){
                    res[0] = 0;
                }
                index = mid+1;
                while(index < nums.length){
                    if(nums[index] != target){
                        res[1] = index-1;
                        break;
                    }
                    index++;
                }
                if(index == nums.length){
                    res[1] = nums.length-1;
                }
            }else if(nums[mid] < target){
                left = mid;
            }else {
                right = mid;
            }

            if(res[0] != -1 && res[1] != -1){
                return res;
            }
        }

        if(nums[left] == target || nums[right] == target){
            int index = left;
            while(index >= 0){
                if(nums[index] != target){
                    res[0] = index+1;
                    break;
                }
                index--;
            }
            if(index == -1){
                res[0] = left;
            }
            index = left+1;
            while(index < nums.length){
                if(nums[index] != target){
                    res[1] = index-1;
                    break;
                }
                index++;
            }
            if(index == nums.length){
                res[1] = nums.length-1;
            }

        }


        return res;

    }

优化后的 二分+递归
设置了标志位,不再进行重复区间的计算

class Solution {
public:
    vector<int> binary_search(vector<int> &nums, int left, int right, int target, int flag) {
        // flag 为一个标志位
        // flag == 0, 还没有找到第一个 target
        // flag == -1, 搜索左边界
        // flag == 1, 搜索右边界
        int mid, x1, x2;
        while (left < right) {
            mid = left + (right - left >> 1);
            if (nums[mid] == target) {
                // 由于边界收缩的设置,不会出现 mid == right 的情况, 但是会出现 left == mid 的情况,这会导致区间无法缩减到长度为一
                // 如果是 mid = left + (right - left >> 1) + 1, left = mid, right = mid-1
                // 就会出现上述情况了
                if (flag != 1) {
                    x1 = mid == right ?  : binary_search(nums, left, mid, target, -1)[0];
                } else {
                    x1 = left;
                }
                if (flag != -1) {
                    x2 = mid == left ? nums[right] == target ? right : mid : binary_search(nums, mid, right, target, 1)[1];
                } else {
                    x2 = right;
                }
                return {x1, x2};
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (nums[left] == target) {
            return {left, right};
        } else {
            return {-1, -1};
        }
    }
    
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()) return {-1, -1};
        return binary_search(nums, 0, nums.size()-1, target, 0);
    }
};

大概是因为重复计算了很多区间

补一个:二分+递归
但是并没有很快

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> binary_search(vector<int> &nums, int left, int right, int target) {
        int mid, x1, x2;
        while (left < right) {
            mid = left + (right - left >> 1);
            if (nums[mid] == target) {
                // 由于边界收缩的设置,不会出现 mid == right 的情况, 但是会出现 left == mid 的情况
                // 如果是 mid = left + (right - left >> 1) + 1, left = mid, right = mid-1
                // 就会出现上述情况了
                x1 = mid == right ?  : binary_search(nums, left, mid, target)[0];
                x2 = mid == left ? nums[right] == target ? right : mid : binary_search(nums, mid, right, target)[1];
                return {x1, x2};
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (nums[left] == target) {
            return {left, right};
        } else {
            return {-1, -1};
        }
    }
    
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()) return {-1, -1};
        return binary_search(nums, 0, nums.size()-1, target);
    }
};

真二分

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int left_binary_search(vector<int> &nums, int left, int right, int target) {
        int mid;
        while (left < right) {
            mid = left + (right - left >> 1);
            if (nums[mid] == target) {
                right = mid;
            } else if (nums[mid] > target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return nums[left] == target ? left : -1;
    }

    int right_binary_search(vector<int> &nums, int left, int right, int target) {
        int mid;
        while (left < right) {
            mid = left + (right - left >> 1) + 1;
            if (nums[mid] == target) {
                left = mid;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return nums[left] == target ? left : -1;
    }

    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()) return {-1, -1};
        int l, r;
        l = 0;
        r = nums.size()-1;
        int x1 = left_binary_search(nums, l, r, target);
        int x2 = right_binary_search(nums, l, r, target);
        return {x1, x2};
    }
};

判断左右边界
执行结果:
通过
显示详情
执行用时:0 ms, 在所有 Java 提交中击败了100.00% 的用户
内存消耗:41.1 MB, 在所有 Java 提交中击败了99.52% 的用户

public int[] searchRange(int[] arr, int findval) {
int[] res=new int[2];
int end =arr.length-1;
int start = 0;
int mid ;

    while (start<=end){
        mid = start+(end-start)/2;
        //查找的值小于中间值即在中间值左边
        if (arr[mid]>findval){
            //结束的位置为中间位置
            end = mid-1;
        }else{
            //查找的值大于中间值即在中间值右边
            if (arr[mid]<findval){
                //开始的位置为中间位置
                start =mid+1;
            }else/*findval等于arr[mid]*/{
                //判断前一个位置是否等于中间位置
                while(mid-1>=0&&arr[mid-1] == findval){
                    mid -=1;
                }
                res[0]=mid;
               
                while(mid+1<=arr.length-1&&arr[mid+1] == findval){

                    mid+=1;
                }
                res[1]=mid;
                return res;
            }
        }
    }
    return  new int[]{-1,-1};
}
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        result = [-1, -1]
        if target not in nums:
            return result
        elif len(nums) == 1:
            result = [0, 0]
            return result 
        else:
            left = 0
            right = len(nums) - 1
            while left + 1 < right:
                mid = (right + left) // 2
                if nums[mid] < target:
                    left = mid
                else:
                    right = mid
            if nums[right - 1] == target:
                result[0] = right - 1
            else:
                result[0] = right
            left = 0
            right = len(nums) - 1
            while left + 1 < right:
                mid = (right + left) // 2
                if nums[mid] > target:
                    right = mid
                else:
                    left = mid
            if nums[left + 1] == target:
                result[1] = left + 1
            else:
                result[1] = left
            return result

我太强了

这个是用的普通版本的二分模板 加上左右扩展边界

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) return new int [] {-1, -1};
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                left = mid - 1;
                right = mid + 1;
                while (left >= 0 && nums[left] == target) left--;
                while (right < nums.length && nums[right] == target) right++;
                return new int [] {++left, --right};
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return new int [] {-1, -1};
    }
}