leetcode34：在排序数组中查询元素的第一个和最后一个位置

题目链接

leetcode

题目描述

给定一个按照非递减顺序排列的整数数组 nums 和一个目标值 target。请找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
设计并实现时间复杂度为 O(log n) 的算法解决此问题。

C++ 代码

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

void printArray(const vector<int>& nums) {
    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i] << " ";
    }
    cout << endl;
}

/*
    两次二分

    第一次二分：
        查找第一个位置，使得它的值大于等于 target，
    第二次二分：
        查找最后一个位置，使得它的值小于等于 target。
    注意：特判边界。

    时间复杂度：O(logn)
        其中 n 为数组的长度。
        二分查找的时间复杂度为 O(logn)，一共会执行两次。
    空间复杂度：O(1)
        只需要常数空间存放若干变量。
*/
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()) return {-1, -1};

        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if (nums[r] != target) return {-1, -1};

        int first = r, last = -1;
        l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (nums[mid] <= target) l = mid;
            else r = mid - 1; 
        }
        last = r;

        return {first, last};
    }
};

/*
    思路同上
*/
class Solution_1 {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = leftBound(nums, target);
        int right = rightBound(nums, target);
        return {left, right};
    }

    int leftBound(const vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] < target) {
                left = mid + 1;  // 区间变为 [mid + 1, right]
            } else if (nums[mid] > target) {
                right = mid - 1; // 区间变为 [left, mid - 1]
            } else if (nums[mid] == target) {
                right = mid - 1; // 收缩右侧边界
            }
        }
        // 检查 left 是否越界
        if (left >= nums.size() || nums[left] != target) return -1;

        return left;
    }

    int rightBound(const vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] < target) {
                left = mid + 1;  // 区间变为 [mid + 1, right]
            } else if (nums[mid] > target) {
                right = mid - 1; // 区间变为 [left, mid - 1]
            } else if (nums[mid] == target) {
                left = mid + 1;  // 收缩左侧边界
            }
        }
        // 检查 right 是否越界
        if (right < 0 || nums[right] != target) return -1;

        return right;
    }
};

int main() {
    Solution solution;
    vector<int> nums = {5, 7, 7, 8, 8, 10};
    printArray(nums);
    int target = 8;
    vector<int> result = solution.searchRange(nums, target);
    cout << "First occurrence of target " << target << " is at index: " << result[0] << endl;
    cout << "Last occurrence of target " << target << " is at index: " << result[1] << endl;
    
    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
   二分查找的两次应用

   第一次二分查找：找到目标值的第一个出现位置。
       如果 nums[mid] 等于目标值，需要检查是否是第一个（mid == 0 或 nums[mid-1] != target）。
       如果不是第一个，继续在左侧查找（right = mid - 1）。
       如果 nums[mid] 小于目标值，继续在右侧查找（left = mid + 1）。
       如果 nums[mid] 大于目标值，继续在左侧查找（right = mid - 1）。
   第二次二分查找：找到目标值的最后一个出现位置。
       如果 nums[mid] 等于目标值，需要检查是否是最后一个（mid == len(nums)-1 或 nums[mid+1] != target）。
       如果不是最后一个，继续在右侧查找（left = mid + 1）。
       如果 nums[mid] 小于目标值，继续在右侧查找（left = mid + 1）。
       如果 nums[mid] 大于目标值，继续在左侧查找（right = mid - 1）。

    时间复杂度：O(logn)
        二分查找：每次查找的时间复杂度为 O(logn)，其中 n 是数组的长度。
        两次查找：总时间复杂度为 O(logn) + O(logn) = O(logn)。
    空间复杂度：O(1)
        常数空间：仅使用了常数级别的额外空间（两个指针），空间复杂度为 O(1)。
*/
// searchRange 返回目标值在排序数组中的第一个和最后一个位置
func searchRange(nums []int, target int) []int {
	if len(nums) == 0 {
		return []int{-1, -1}
	}

	// 查找目标值的第一个位置
	first := findFirst(nums, target)
	if first == -1 {
		return []int{-1, -1}
	}
	// 查找目标值的最后一个位置
	last := findLast(nums, target)

	return []int{first, last}
}

// findFirst 查找目标值的第一个位置
func findFirst(nums []int, target int) int {
	left, right := 0, len(nums) - 1

	for left <= right {
		mid := left + (right - left) / 2
		if nums[mid] < target {
			left = mid + 1
		} else if nums[mid] > target {
			right = mid - 1
		} else {
			if mid == 0 || nums[mid-1] != target {
				return mid
			}
			right = mid - 1
		}
	}
	return -1
}

// findLast 查找目标值的最后一个位置
func findLast(nums []int, target int) int {
	left, right := 0, len(nums) - 1
	
	for left <= right {
		mid := left + (right - left) / 2
		if nums[mid] < target {
			left = mid + 1
		} else if nums[mid] > target {
			right = mid - 1
		} else {
			if mid == len(nums) - 1 || nums[mid+1] != target {
				return mid
			}
			left = mid + 1
		}
	}
	return -1
}

func main() {
	// 测试用例
	testCases := []struct {
		nums      []int
		target    int
		expected  []int
	}{
		{[]int{5, 7, 7, 8, 8, 10}, 8, []int{3, 4}},
		{[]int{5, 7, 7, 8, 8, 10}, 6, []int{-1, -1}},
		{[]int{}, 0, []int{-1, -1}},
	}

	for i, tc := range testCases {
		result := searchRange(tc.nums, tc.target)
        fmt.Printf("Test Case %d: Input: nums = %v, target = %d\n", i+1, tc.nums, tc.target)
		
        if fmt.Sprint(result) == fmt.Sprint(tc.expected) {
			fmt.Printf("Output: %v, PASS\n", result)
		} else {
			fmt.Printf("Output: %v, FAIL (Expected: %v)\n", result, tc.expected)
		}
	}
}