- 正确答案：在旋转排序数组中搜索目标值，应使用修改版的二分查找算法，时间复杂度O(log n)。核心思想是：每次二分后，左右两段必有一段是严格升序的；通过判断mid位置与left/right的大小关系，确定哪一段有序，再结合target是否落在该有序段内，决定搜索方向。 - 解答思路： 1. 初始化left=0, right=n-1； 2. 循环条件为left <= right； 3. 计算mid = left + (right - left) / 2； 4. 若nums[mid] == target，直接返回mid； 5. 否则判断左半段[nums[left], nums[mid]]是否有序（即nums[left] <= nums[mid]）： - 若有序：检查target是否在[left, mid)范围内（即nums[left] <= target < nums[mid]），若是则right = mid - 1，否则left = mid + 1； - 若无序（即右半段有序）：检查target是否在(mid, right]范围内（即nums[mid] < target <= nums[right]），若是则left = mid + 1，否则right = mid - 1； 6. 循环结束未找到，返回-1。 - 深度知识讲解：本题考察对二分查找本质的深刻理解——二分不依赖“全局有序”，而依赖“每次划分后能排除一半搜索空间”的决策能力。旋转数组虽整体无序，但任意中点切分后，必有一侧子区间保持单调性（数学证明：设原数组升序，旋转点k∈[0,n)，则数组形如 [A[k],...,A[n-1],A[0],...,A[k-1]]；对任意mid，若mid < k，则左段跨旋转点→无序，右段A[mid+1..n-1]∪A[0..k-1]可能不连续；但更严谨的判定是：比较nums[left]与nums[mid]——若nums[left] <= nums[mid]，说明left到mid未跨越旋转点，故该段严格递增；反之则mid到right必为递增段）。该性质保证了每次都能基于target与端点值的大小关系安全地收缩区间。注意边界细节：等号处理（如nums[left] <= nums[mid]中的=，对应left==mid场景，此时左段长度为1，天然有序）；target比较时用<而非<=（因mid已排除）；整数除法向下取整不影响正确性，但需避免(left+right)溢出，故推荐left + (right-left)/2。该算法稳定、原地、不依赖额外空间，是经典“二分变形”范式，延伸问题包括LC81（含重复元素）、LC153（找最小值）、LC154（含重复找最小值）。 - 代码示例（Java风格伪代码，可直接运行）： ``` public int search(int[] nums, int target) { if (nums == null || nums.length == 0) return -1; int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } // 判断左段是否有序 if (nums[left] <= nums[mid]) { // 左段有序：检查target是否在左段范围内 if (nums[left] <= target && target < nums[mid]) { right = mid - 1; } else { left = mid + 1; } } else { // 右段有序：检查target是否在右段范围内 if (nums[mid] < target && target <= nums[right]) { left = mid + 1; } else { right = mid - 1; } } } return -1; } ``` - 扩展知识： 1. 若数组含重复元素（LC81），则nums[left] == nums[mid] == nums[right]时无法判断哪边有序，最坏退化为O(n)，需跳过重复：while(left < right && nums[left] == nums[left+1]) left++；同理处理right。 2. 找旋转数组最小值（LC153）：同样二分，比较nums[mid]与nums[right]——若nums[mid] > nums[right]，最小值在右半；否则在左半（含mid）。 3. 底层视角：该算法体现了“信息论”思想——每次比较获取至少1 bit信息（有序/无序 + target位置倾向），支撑log n效率；其循环不变量为：target若存在，必在[left, right]闭区间内。 4. 实际工程中，此类问题常见于日志索引、时间序列数据库的分段存储（按时间旋转切片），要求低延迟随机查找。

京东科技 llm算法日常实习 面经分享

全站热榜

创作者周榜

京东科技 llm算法日常实习面经分享