千问 LeetCode 33. 搜索旋转排序数组 Golang实现

LeetCode 33 搜索旋转排序数组的 Golang 实现核心思路依然是改造二分查找每次二分后利用旋转数组的特性至少有一半是有序的先判断哪半部分有序再判断 target 是否落在有序区间内从而决定收缩左边界还是右边界。Golang 代码实现func search(nums []int, target int) int {left, right : 0, len(nums)-1for left right { // 计算中点这种写法可以防止 leftright 整数溢出 mid : left (right-left)/2 // 找到目标直接返回下标 if nums[mid] target { return mid } // 判断左半部分 [left, mid] 是否有序 if nums[left] nums[mid] { // 左半部分有序判断 target 是否在左半范围内 // 注意右边界是开区间因为 nums[mid] 已经判断过不等于 target if nums[left] target target nums[mid] { right mid - 1 } else { left mid 1 } } else { // 左半部分无序则右半部分 [mid, right] 一定有序 // 判断 target 是否在右半范围内 if nums[mid] target target nums[right] { left mid 1 } else { right mid - 1 } } } // 未找到目标返回 -1 return -1}Golang 实现的关键细节防止整数溢出在 Golang 中虽然 int 类型通常是 64 位但在处理极大数组时left right 依然有溢出风险。使用 left (right-left)/2 是标准的防溢出写法。边界条件 与 的精准控制nums[left] nums[mid]当 left mid 时区间只剩一个元素左半部分“有序”是成立的此处必须用 。target nums[mid]因为 nums[mid] target 的情况已经在最前面判断过了所以在判断区间范围时右边界使用开区间即可。时间复杂度标准的二分查找时间复杂度为 O(log n)空间复杂度为 O(1)。这道题是面试中非常高频的二分查找变体核心在于不要试图去还原整个数组的排序而是利用“局部有序”的性质进行折半排除。需要我顺带把 Golang 版的 LeetCode 81含重复元素的搜索旋转排序数组也写出来吗重复元素会让边界判断增加一个去重步骤。