Skip to content

Latest commit

 

History

History
633 lines (556 loc) · 22.4 KB

0034.在排序数组中查找元素的第一个和最后一个位置.md

File metadata and controls

633 lines (556 loc) · 22.4 KB
Raw

参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！

34. 在排序数组中查找元素的第一个和最后一个位置

题目链接

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：你可以设计并实现时间复杂度为 $O(\log n)$ 的算法解决此问题吗？

示例 1：

  • 输入：nums = [5,7,7,8,8,10], target = 8
  • 输出：[3,4]

示例 2：

  • 输入：nums = [5,7,7,8,8,10], target = 6
  • 输出：[-1,-1]

示例 3：

  • 输入：nums = [], target = 0
  • 输出：[-1,-1]

思路

这道题目如果基础不是很好，不建议大家看简短的代码，简短的代码隐藏了太多逻辑，结果就是稀里糊涂把题AC了，但是没有想清楚具体细节！

对二分还不了解的同学先做这两题：

下面我来把所有情况都讨论一下。

寻找target在数组里的左右边界，有如下三种情况：

  • 情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返回{-1, -1}
  • 情况二：target 在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1}
  • 情况三：target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}

这三种情况都考虑到，说明就想的很清楚了。

接下来，在去寻找左边界，和右边界了。

采用二分法来去寻找左右边界，为了让代码清晰，我分别写两个二分来寻找左边界和右边界。

刚刚接触二分搜索的同学不建议上来就想用一个二分来查找左右边界，很容易把自己绕进去，建议扎扎实实的写两个二分分别找左边界和右边界

寻找右边界

先来寻找右边界，至于二分查找，如果看过704.二分查找就会知道，二分查找中什么时候用while (left <= right)，有什么时候用while (left < right)，其实只要清楚循环不变量，很容易区分两种写法。

那么这里我采用while (left <= right)的写法，区间定义为[left, right]，即左闭右闭的区间（如果这里有点看不懂了，强烈建议把704.二分查找这篇文章先看了，704题目做了之后再做这道题目就好很多了）

确定好：计算出来的右边界是不包含target的右边界，左边界同理。

可以写出如下代码

// 二分查找，寻找target的右边界（不包括target）
// 如果rightBorder为没有被赋值（即target在数组范围的左边，例如数组[3,3]，target为2），为了处理情况一
int getRightBorder(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
    int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况
    while (left <= right) { // 当left==right，区间[left, right]依然有效
        int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
        if (nums[middle] > target) {
            right = middle - 1; // target 在左区间，所以[left, middle - 1]
        } else { // 当nums[middle] == target的时候，更新left，这样才能得到target的右边界
            left = middle + 1;
            rightBorder = left;
        }
    }
    return rightBorder;
}

寻找左边界

// 二分查找，寻找target的左边界leftBorder（不包括target）
// 如果leftBorder没有被赋值（即target在数组范围的右边，例如数组[3,3],target为4），为了处理情况一
int getLeftBorder(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
    int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况
    while (left <= right) {
        int middle = left + ((right - left) / 2);
        if (nums[middle] >= target) { // 寻找左边界，就要在nums[middle] == target的时候更新right
            right = middle - 1;
            leftBorder = right;
        } else {
            left = middle + 1;
        }
    }
    return leftBorder;
}

处理三种情况

左右边界计算完之后，看一下主体代码，这里把上面讨论的三种情况，都覆盖了

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int leftBorder = getLeftBorder(nums, target);
        int rightBorder = getRightBorder(nums, target);
        // 情况一
        if (leftBorder == -2 || rightBorder == -2) return {-1, -1};
        // 情况三
        if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1};
        // 情况二
        return {-1, -1};
    }
private:
     int getRightBorder(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] > target) {
                right = middle - 1;
            } else { // 寻找右边界，nums[middle] == target的时候更新left
                left = middle + 1;
                rightBorder = left;
            }
        }
        return rightBorder;
    }
    int getLeftBorder(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] >= target) { // 寻找左边界，nums[middle] == target的时候更新right
                right = middle - 1;
                leftBorder = right;
            } else {
                left = middle + 1;
            }
        }
        return leftBorder;
    }
};

这份代码在简洁性很有大的优化空间，例如把寻找左右区间函数合并一起。

但拆开更清晰一些，而且把三种情况以及对应的处理逻辑完整的展现出来了。

总结

初学者建议大家一块一块的去分拆这道题目，正如本题解描述，想清楚三种情况之后，先专注于寻找右区间，然后专注于寻找左区间，左右根据左右区间做最后判断。

不要上来就想如果一起寻找左右区间，搞着搞着就会顾此失彼，绕进去拔不出来了。

其他语言版本

Java

class Solution {
    int[] searchRange(int[] nums, int target) {
        int leftBorder = getLeftBorder(nums, target);
        int rightBorder = getRightBorder(nums, target);
        // 情况一
        if (leftBorder == -2 || rightBorder == -2) return new int[]{-1, -1};
        // 情况三
        if (rightBorder - leftBorder > 1) return new int[]{leftBorder + 1, rightBorder - 1};
        // 情况二
        return new int[]{-1, -1};
    }

    int getRightBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] > target) {
                right = middle - 1;
            } else { // 寻找右边界，nums[middle] == target的时候更新left
                left = middle + 1;
                rightBorder = left;
            }
        }
        return rightBorder;
    }

    int getLeftBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] >= target) { // 寻找左边界，nums[middle] == target的时候更新right
                right = middle - 1;
                leftBorder = right;
            } else {
                left = middle + 1;
            }
        }
        return leftBorder;
    }
}
// 解法2
// 1、首先，在 nums 数组中二分查找 target；
// 2、如果二分查找失败，则 binarySearch 返回 -1，表明 nums 中没有 target。此时，searchRange 直接返回 {-1, -1}；
// 3、如果二分查找成功，则 binarySearch 返回 nums 中值为 target 的一个下标。然后，通过左右滑动指针，来找到符合题意的区间

class Solution {
	public int[] searchRange(int[] nums, int target) {
		int index = binarySearch(nums, target); // 二分查找
		
		if (index == -1) { // nums 中不存在 target，直接返回 {-1, -1}
			return new int[] {-1, -1}; // 匿名数组 
		}
		// nums 中存在 targe，则左右滑动指针，来找到符合题意的区间
		int left = index;
		int right = index;
        // 向左滑动，找左边界
		while (left - 1 >= 0 && nums[left - 1] == nums[index]) { // 防止数组越界。逻辑短路，两个条件顺序不能换
			left--;
		}
        // 向左滑动，找右边界
		while (right + 1 < nums.length && nums[right + 1] == nums[index]) { // 防止数组越界。
			right++;
		}
		return new int[] {left, right};
    }
	
	/**
	 * 二分查找
	 * @param nums
	 * @param target
	 */
	public int binarySearch(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) {
				return mid;
			} else if (nums[mid] < target) {
				left = mid + 1;
			} else {
				right = mid - 1; // 不变量：左闭右闭区间
			}
		}
		return -1; // 不存在
	}
}

Python

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def getRightBorder(nums:List[int], target:int) -> int:
            left, right = 0, len(nums)-1
            rightBoder = -2 # 记录一下rightBorder没有被赋值的情况
            while left <= right:
                middle = left + (right-left) // 2
                if nums[middle] > target:
                    right = middle - 1
                else: # 寻找右边界，nums[middle] == target的时候更新left
                    left = middle + 1
                    rightBoder = left
    
            return rightBoder
        
        def getLeftBorder(nums:List[int], target:int) -> int:
            left, right = 0, len(nums)-1 
            leftBoder = -2 # 记录一下leftBorder没有被赋值的情况
            while left <= right:
                middle = left + (right-left) // 2
                if nums[middle] >= target: #  寻找左边界，nums[middle] == target的时候更新right
                    right = middle - 1;
                    leftBoder = right;
                else:
                    left = middle + 1
            return leftBoder
        leftBoder = getLeftBorder(nums, target)
        rightBoder = getRightBorder(nums, target)
        # 情况一
        if leftBoder == -2 or rightBoder == -2: return [-1, -1]
        # 情况三
        if rightBoder -leftBoder >1: return [leftBoder + 1, rightBoder - 1]
        # 情况二
        return [-1, -1]
# 解法2
# 1、首先，在 nums 数组中二分查找 target；
# 2、如果二分查找失败，则 binarySearch 返回 -1，表明 nums 中没有 target。此时，searchRange 直接返回 {-1, -1}；
# 3、如果二分查找成功，则 binarySearch 返回 nums 中值为 target 的一个下标。然后，通过左右滑动指针，来找到符合题意的区间
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def binarySearch(nums:List[int], target:int) -> int:
            left, right = 0, len(nums)-1
            while left<=right: # 不变量：左闭右闭区间
                middle = left + (right-left) // 2
                if nums[middle] > target:
                    right = middle - 1
                elif nums[middle] < target: 
                    left = middle + 1
                else:
                    return middle
            return -1
        index = binarySearch(nums, target)
        if index == -1:return [-1, -1] # nums 中不存在 target，直接返回 {-1, -1}
        # nums 中存在 targe，则左右滑动指针，来找到符合题意的区间
        left, right = index, index
        # 向左滑动，找左边界
        while left -1 >=0 and nums[left - 1] == target: left -=1
        # 向右滑动，找右边界
        while right+1 < len(nums) and nums[right + 1] == target: right +=1
        return [left, right]
# 解法3
# 1、首先，在 nums 数组中二分查找得到第一个大于等于 target的下标（左边界）与第一个大于target的下标（右边界）；
# 2、如果左边界<= 右边界，则返回 [左边界, 右边界]。否则返回[-1, -1]
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def binarySearch(nums:List[int], target:int, lower:bool) -> int:
            left, right = 0, len(nums)-1
            ans = len(nums)
            while left<=right: # 不变量：左闭右闭区间
                middle = left + (right-left) //2 
                # lower为True，执行前半部分，找到第一个大于等于 target的下标 ，否则找到第一个大于target的下标
                if nums[middle] > target or (lower and nums[middle] >= target): 
                    right = middle - 1
                    ans = middle
                else: 
                    left = middle + 1
            return ans

        leftBorder = binarySearch(nums, target, True) # 搜索左边界
        rightBorder = binarySearch(nums, target, False) -1  # 搜索右边界
        if leftBorder<= rightBorder and rightBorder< len(nums) and nums[leftBorder] == target and  nums[rightBorder] == target:
            return [leftBorder, rightBorder]
        return [-1, -1]
# 解法4
# 1、首先，在 nums 数组中二分查找得到第一个大于等于 target的下标leftBorder；
# 2、在 nums 数组中二分查找得到第一个大于等于 target+1的下标， 减1则得到rightBorder；
# 3、如果开始位置在数组的右边或者不存在target，则返回[-1, -1] 。否则返回[leftBorder, rightBorder]
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def binarySearch(nums:List[int], target:int) -> int:
            left, right = 0, len(nums)-1
            while left<=right: # 不变量：左闭右闭区间
                middle = left + (right-left) //2 
                if nums[middle] >= target: 
                    right = middle - 1
                else: 
                    left = middle + 1
            return left  # 若存在target，则返回第一个等于target的值 

        leftBorder = binarySearch(nums, target) # 搜索左边界
        rightBorder = binarySearch(nums, target+1) -1  # 搜索右边界
        if leftBorder == len(nums) or nums[leftBorder]!= target: # 情况一和情况二
            return [-1, -1]
        return [leftBorder, rightBorder]

Go

func searchRange(nums []int, target int) []int {
    leftBorder := getLeft(nums, target)
    rightBorder := getRight(nums, target)
    // 情况一
    if leftBorder == -2 || rightBorder == -2 {
        return []int{-1, -1}
    }
    // 情况三
    if rightBorder - leftBorder > 1 {
        return []int{leftBorder + 1, rightBorder - 1}
    }
    // 情况二
    return []int{-1, -1}
}

func getLeft(nums []int, target int) int {
    left, right := 0, len(nums)-1
    border := -2 // 记录border没有被赋值的情况；这里不能赋值-1，target = num[0]时，会无法区分情况一和情况二
    for left <= right { // []闭区间
	mid := left + ((right - left) >> 1)
	if nums[mid] >= target { // 找到第一个等于target的位置
	    right = mid - 1
            border = right
	} else {
	    left =  mid + 1
	}
    }
    return border
}

func getRight(nums []int, target int) int {
    left, right := 0, len(nums) - 1
    border := -2
    for left <= right {
	mid := left + ((right - left) >> 1)
	if nums[mid] > target { 
		right = mid - 1
	} else { // 找到第一个大于target的位置
	    left = mid + 1
            border = left
	}
    }
    return border

}

JavaScript

var searchRange = function(nums, target) {
    const getLeftBorder = (nums, target) => {
        let left = 0, right = nums.length - 1;
        let leftBorder = -2;// 记录一下leftBorder没有被赋值的情况
        while(left <= right){
            let middle = left + ((right - left) >> 1);
            if(nums[middle] >= target){ // 寻找左边界，nums[middle] == target的时候更新right
                right = middle - 1;
                leftBorder = right;
            } else {
                left = middle + 1;
            }
        }
        return leftBorder;
    }

    const getRightBorder = (nums, target) => {
        let left = 0, right = nums.length - 1;
        let rightBorder = -2; // 记录一下rightBorder没有被赋值的情况
        while (left <= right) {
            let middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle - 1;
            } else { // 寻找右边界，nums[middle] == target的时候更新left
                left = middle + 1;
                rightBorder = left;
            }
        }
        return rightBorder;
    }

    let leftBorder = getLeftBorder(nums, target);
    let rightBorder = getRightBorder(nums, target);
    // 情况一
    if(leftBorder === -2 || rightBorder === -2) return [-1,-1];
    // 情况三
    if (rightBorder - leftBorder > 1) return [leftBorder + 1, rightBorder - 1];
    // 情况二
    return [-1, -1];
};

TypeScript

function searchRange(nums: number[], target: number): number[] {
    const leftBoard: number = getLeftBorder(nums, target);
    const rightBoard: number = getRightBorder(nums, target);
    // target 在nums区间左侧或右侧
    if (leftBoard === (nums.length - 1) || rightBoard === 0) return [-1, -1];
    // target 不存在与nums范围内
    if (rightBoard - leftBoard <= 1) return [-1, -1];
    // target 存在于nums范围内
    return [leftBoard + 1, rightBoard - 1];
};
// 查找第一个大于target的元素下标
function getRightBorder(nums: number[], target: number): number {
    let left: number = 0,
        right: number = nums.length - 1;
    // 0表示target在nums区间的左边
    let rightBoard: number = 0;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] <= target) {
            // 右边界一定在mid右边（不含mid）
            left = mid + 1;
            rightBoard = left;
        } else {
            // 右边界在mid左边（含mid）
            right = mid - 1;
        }
    }
    return rightBoard;
}
// 查找第一个小于target的元素下标
function getLeftBorder(nums: number[], target: number): number {
    let left: number = 0,
        right: number = nums.length - 1;
    // length-1表示target在nums区间的右边
    let leftBoard: number = nums.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] >= target) {
            // 左边界一定在mid左边（不含mid）
            right = mid - 1;
            leftBoard = right;
        } else {
            // 左边界在mid右边（含mid）
            left = mid + 1;
        }
    }
    return leftBoard;
}

Scala

object Solution {
  def searchRange(nums: Array[Int], target: Int): Array[Int] = {
    var left = getLeftBorder(nums, target)
    var right = getRightBorder(nums, target)
    if (left == -2 || right == -2) return Array(-1, -1)
    if (right - left > 1) return Array(left + 1, right - 1)
    Array(-1, -1)
  }

  // 寻找左边界
  def getLeftBorder(nums: Array[Int], target: Int): Int = {
    var leftBorder = -2
    var left = 0
    var right = nums.length - 1
    while (left <= right) {
      var mid = left + (right - left) / 2
      if (nums(mid) >= target) {
        right = mid - 1
        leftBorder = right
      } else {
        left = mid + 1
      }
    }
    leftBorder
  }

  // 寻找右边界
  def getRightBorder(nums: Array[Int], target: Int): Int = {
    var rightBorder = -2
    var left = 0
    var right = nums.length - 1
    while (left <= right) {
      var mid = left + (right - left) / 2
      if (nums(mid) <= target) {
        left = mid + 1
        rightBorder = left
      } else {
        right = mid - 1
      }
    }
    rightBorder
  }
}

Kotlin

class Solution {
    fun searchRange(nums: IntArray, target: Int): IntArray {
        var index = binarySearch(nums, target)
        // 没找到，返回[-1, -1]
        if (index == -1) return intArrayOf(-1, -1)
        var left = index
        var right = index
        // 寻找左边界
        while (left - 1 >=0 && nums[left - 1] == target){
            left--
        }
        // 寻找右边界
        while (right + 1 <nums.size && nums[right + 1] == target){
            right++
        }
        return intArrayOf(left, right)
    }
    // 二分查找常规写法
    fun binarySearch(nums: IntArray, target: Int): Int {
        var left = 0;
        var right = nums.size - 1
        while (left <= right) {
            var middle = left + (right - left)/2
            if (nums[middle] > target) {
                right = middle - 1
            }
            else {
                if (nums[middle] < target) {
                    left = middle + 1
                }
                else {
                    return middle
                }
            }
        }
        // 没找到，返回-1
        return -1
    }
}