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

悠悠 2023-09-27 22:05 97阅读 0赞

**目录**

题目来源

题目描述

示例

提示

题目解析

算法源码

--------------------

### 题目来源 ###

[34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）][34. _ - _LeetCode]

### 题目描述 ###

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

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

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

### 示例 ###

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:102px;">输入</td> 
   <td style="width:396px;">nums = [5,7,7,8,8,10], target = 8</td> 
  </tr> 
  <tr> 
   <td style="width:102px;">输出</td> 
   <td style="width:396px;">[3,4]</td> 
  </tr> 
  <tr> 
   <td style="width:102px;">说明</td> 
   <td style="width:396px;">无</td> 
  </tr> 
 </tbody> 
</table>

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:102px;">输入</td> 
   <td style="width:396px;">nums = [5,7,7,8,8,10], target = 6</td> 
  </tr> 
  <tr> 
   <td style="width:102px;">输出</td> 
   <td style="width:396px;">[-1,-1]</td> 
  </tr> 
  <tr> 
   <td style="width:102px;">说明</td> 
   <td style="width:396px;">无</td> 
  </tr> 
 </tbody> 
</table>

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:102px;">输入</td> 
   <td style="width:396px;">nums = [], target = 0</td> 
  </tr> 
  <tr> 
   <td style="width:102px;">输出</td> 
   <td style="width:396px;">[-1,-1]</td> 
  </tr> 
  <tr> 
   <td style="width:102px;">说明</td> 
   <td style="width:396px;">无</td> 
  </tr> 
 </tbody> 
</table>

### 提示 ###

*  0 <= nums.length <= 105
 *  \-109 <= nums\[i\] <= 109
 *  nums 是一个非递减数组
 *  \-109 <= target <= 109

### 题目解析 ###

本题的nums是一个非递减顺序排列的整数数组 nums，则说明nums中是存在重复数值的，因此本题要查找的元素有第一个和最后一个位置的概念。

本题要我们在O(logN)的时间复杂度内完成元素的第一个和最后一个位置的查找，这很容易联想到二分查找，因为本题nums是一个单调的，而二分的时间复杂度也是O(logN)

但是常用的二分查找，比如Java语言的Arrays.binarySearch，并不适用于找有重复值的元素的位置，比如下面代码最终返回的要查找元素1的位置是索引2。

import java.util.Arrays;
    
    public class Main {
      public static void main(String[] args) {
        int[] arr = {1, 1, 1, 1, 1};
        System.out.println(Arrays.binarySearch(arr, 1));
      }
    }

这和底层二分查找的策略有关，关于二分查找，可以看下这篇博客中关于二分查找的实现：

[算法设计 - 二分法和三分法，洛谷P3382\_伏城之外的博客-CSDN博客][- _P3382_-CSDN]

下面给出三种语言的标准二分查找实现

Java 标准二分查找实现

import java.util.*;
     
    public class Main {
      public static void main(String[] args) {
    	  int[] arr = {1,1,1,1,1};
    	  System.out.println(binarySearch(arr, 1));
      }
      
      public static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;
    
        while (low <= high) {
          int mid = (low + high) >> 1;
          int midVal = arr[mid];
    
          if (midVal > target) {
            high = mid - 1;
          } else if (midVal < target) {
            low = mid + 1;
          } else {
            return mid; // midVal == target，则直接返回mid作为target的位置
          }
        }
    
        return -low - 1; // 找不到则返回插入位置
      }
    }

JavaScript标准二分查找实现

Python 二分查找标准实现

def binarySearch(arr, target):
        low = 0
        high = len(arr) - 1
    
        while low <= high:
            mid = (low + high) >> 1
            midVal = arr[mid]
    
            if midVal > target:
                high = mid - 1
            elif midVal < target:
                low = mid + 1
            else:
                return mid
    
        return -low - 1

标准的二分查找框架中，如果midVal == target时，是直接返回了此时的mid值作为了target的位置。

但是如果target有多个重复值元素的话，那么在midVal == target时，不应该武断地判定mid就是target的位置，而是应该尝试向mid位置的左右方向进行延伸判断：

向mid位置的左边进行延伸判断：

*  如果 mid == 0 或 arr\[mid\] != arr\[mid-1\]，则说明当前mid位置已经是 target数域 的左边界了，即target第一次出现的位置
 *  如果 mid > 0 且 arr\[mid\] == arr\[mid - 1\]，则说明target数域的左边界还在mid位置的左边，此时为了找到左边界，我们应该让 high = mid - 1

向mid位置右边进行延伸判断：

*  如果 mid == arr.length - 1 或者 arr\[mid\] != arr\[mid + 1\]，则说明按当前mid位置已经是 target数域 的右边界了，即target最后一次出现的位置
 *  如果 mid < nums.length -1 且 arr\[mid\] == arr\[mid+1\]，则说明target数域的右边界还在mid位置的右边，此时为了找到右边界，我们应该让 low = mid + 1

实现代码如下：

Java实现代码

import java.util.*;
     
    public class Main {
      public static void main(String[] args) {
    	  int[] arr = {1,1,1,1,1};
    	  System.out.println(binarySearch(arr, 1));
      }
      
      public static int searchFirst(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;
    
        while (low <= high) {
          int mid = (low + high) >> 1;
          int midVal = arr[mid];
    
          if (midVal > target) {
            high = mid - 1;
          } else if (midVal < target) {
            low = mid + 1;
          } else {
    		// 向左延伸判断，mid是否为target数域的左边界，即第一次出现的位置
    		if(mid == 0 || arr[mid] != arr[mid - 1]) {
    			return mid;
    		} else {
    			high = mid - 1;
    		}
          }
        }
    
        return -low - 1; // 找不到则返回插入位置
      }
      
      public static int searchLast(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;
    
        while (low <= high) {
          int mid = (low + high) >> 1;
          int midVal = arr[mid];
    
          if (midVal > target) {
            high = mid - 1;
          } else if (midVal < target) {
            low = mid + 1;
          } else {
    		// 向右延伸判断，mid是否为target数域的右边界，即最后一次出现的位置
    		if(mid == nums.length - 1 || arr[mid] != arr[mid + 1]) {
    			return mid;
    		} else {
    			low = mid + 1;
    		}
          }
        }
    
        return -low - 1; // 找不到则返回插入位置
      }
    }

JavaScript实现代码

Python实现代码

def searchFirst(arr, target):
        low = 0
        high = len(arr) - 1
    
        while low <= high:
            mid = (low + high) >> 1
            midVal = arr[mid]
    
            if midVal > target:
                high = mid - 1
            elif midVal < target:
                low = mid + 1
            else:
                if mid == 0 or arr[mid] != arr[mid - 1]:
                    return mid
                else:
                    high = mid - 1
    
        return -low - 1
    
    
    def searchLast(arr, target):
        low = 0
        high = len(arr) - 1
    
        while low <= high:
            mid = (low + high) >> 1
            midVal = arr[mid]
    
            if midVal > target:
                high = mid - 1
            elif midVal < target:
                low = mid + 1
            else:
                if mid == len(arr) - 1 or arr[mid] != arr[mid + 1]:
                    return mid
                else:
                    low = mid + 1
    
        return -low - 1

### Java算法源码 ###

class Solution {
        public int[] searchRange(int[] nums, int target) {
            return new int[]{search(nums, target, true), search(nums, target, false)};
        }
    
        public int search(int[] nums, int target, boolean isFirst) {
            int low = 0;
            int high = nums.length - 1;
    
            while(low <= high) {
                int mid = (low + high) >> 1;
                int midVal = nums[mid];
    
                if(midVal > target) {
                    high = mid - 1;
                } else if(midVal < target) {
                    low = mid + 1;
                } else {
                    if(isFirst) {
                        // 查找元素的第一个位置
                        if(mid == 0 || nums[mid] != nums[mid-1]){
                            return mid;
                        } else {
                            high = mid - 1;
                        }
                    } else {
                        // 查找元素的最后一个位置
                        if(mid == nums.length - 1 || nums[mid] != nums[mid + 1]) {
                            return mid;
                        } else {
                            low = mid + 1;
                        }
                    }
                    
                }
            }
    
            return -1;
        }
    }

![5c0f0c038e154743b0657311a887c041.png][]

### JavaScript算法源码 ###

/**
     * @param {number[]} nums
     * @param {number} target
     * @return {number[]}
     */
    var searchRange = function(nums, target) {
        function search(nums, target, isFirst) {
            let low = 0;
            let high = nums.length - 1;
    
            while(low <= high) {
                const mid = (low + high) >> 1;
                const midVal = nums[mid];
    
                if(midVal > target) {
                    high = mid - 1;
                } else if(midVal < target) {
                    low = mid + 1;
                } else {
                    if(isFirst) {
                        if(mid == 0 || nums[mid] != nums[mid-1]) {
                            return mid;
                        } else {
                            high = mid - 1;
                        }
                    } else {
                        if(mid == nums.length - 1 || nums[mid] != nums[mid + 1]) {
                            return mid;
                        } else {
                            low = mid + 1;
                        }
                    }
                }
            }
    
            return -1;
        }
    
        return [search(nums, target, true), search(nums, target, false)];
    };

![17947867206248cfa22babb24ef53809.png][]

### Python算法源码 ###

class Solution(object):
        def searchRange(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            return self.search(nums, target, True), self.search(nums, target, False)
        
        def search(self, nums, target, isFirst):
            low = 0
            high = len(nums) - 1
    
            while low <= high:
                mid = (low + high) >> 1
                midVal = nums[mid]
    
                if midVal > target:
                    high = mid - 1
                elif midVal < target:
                    low = mid + 1
                else:
                    if isFirst:
                        if mid == 0 or nums[mid] != nums[mid-1]:
                            return mid
                        else:
                            high = mid - 1
                    else:
                        if mid == len(nums) - 1 or nums[mid] != nums[mid + 1]:
                            return mid
                        else:
                            low = mid + 1
            
            return -1

![e978f91866a548c98bac77cc3845ef91.png][]

[34. _ - _LeetCode]: https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
[- _P3382_-CSDN]: https://fcqian.blog.csdn.net/article/details/130097676
[5c0f0c038e154743b0657311a887c041.png]: https://img-blog.csdnimg.cn/5c0f0c038e154743b0657311a887c041.png
[17947867206248cfa22babb24ef53809.png]: https://img-blog.csdnimg.cn/17947867206248cfa22babb24ef53809.png
[e978f91866a548c98bac77cc3845ef91.png]: https://img-blog.csdnimg.cn/e978f91866a548c98bac77cc3845ef91.png