64 搜索平移递增数组中的元素
1.题目描述
从平移递增数组中找到target的下标，没有找到就返回-1比如：
1 2 3 4 5 6满足要求
4 5 6 1 2 3 满足要求
7 9 4 5 6 满足
1 7 4 5 6 8 9 不满足，因为不是递增数组平移后的
总之就是，数组左边部分的元素一定大于右边部分的元素，要么就没有平移全部递增
[大，大+，小，小+]
思路：
- 先找到大+这个下标，也就是polit
- 用二分找，可以用nums[mid]和nums[left]来比
- 如果nums[mid]>nums[left]表示左半部分是有序的，没有出现分段点，我们去右边找left=mid+1
- 如果nums[mid]<nums[left]表示[left,mid]不是递增的,分段点一定在左半部分，right = mid-1
关于上面这一条为什么nums[mid]>nums[left]就去右边找呢？一开始up也认为如果我给一个数组nums = {1 7 2 3 4}分段点也不在[mid+1,right]里面呀？原因在对题目的理解错了，题目是一个有序数组平移了，我们把给出的数组平移下，{2 3 4 1 7}并不是严格递增的数组平移得到的不满足题意，不可以用二分找polit，这个数组是两个有序数组拼接的数组，叫“山脉数组”，这就是对题目理解有所偏差导致的疑问了，一开始up也半天没看明白题目要我干啥。。
- nums[mid] = nums[left]的时候left = mid +1,比如数组nums = {1,3}保证循环跳出去，不做相等的时候判定就会进入死循环
- 找到分界点后，判断target在那一部分然后进行二分就行了，不判断也行，两边都二分一下就行了,和nums[0]做比较就行了，依据任然是该平移递增数组的性质
// 1. 二分查找子函数（仅负责有序区间的target查找） int binary_search(int *nums, int left, int right, int numsSize, int target) { while (left <= right) { int mid = left + (right - left) / 2; // 避免溢出 if (nums[mid] == target) { return mid; } else if (nums[mid] > target) { right = mid - 1; } else { left = mid + 1; } } return -1; } // 2. 独立的分段点查找函数（仅负责找旋转排序数组的分段点） // 返回值：分段点下标；数组完全递增（无分段点）返回-1 int find_split_point(int* nums, int numsSize) { if (numsSize <= 1) { // 单元素/空数组无分段点 return -1; } int left = 0; int right = numsSize - 1; while (left <= right) { int mid = left + (right - left) / 2; // 核心：找到分段点（前大后小的位置），立即返回 if (mid < numsSize - 1 && nums[mid] > nums[mid + 1]) { return mid; } // 缩小区间：判断哪一段是有序的 if (nums[mid] > nums[left]) { // 左段有序 → 分段点在右段 left = mid + 1; } else if (nums[mid] < nums[left]) { // 右段有序 → 分段点在左段 right = mid - 1; } else if(nums[mid]==nums[left]){ // 处理nums[mid] == nums[left]（避免死循环，比如[1,3]） left = mid +1; } } // 循环结束未找到 → 数组完全递增，无分段点 return -1; } // 3. 主搜索函数（串联分段点查找+二分查找） int search(int* nums, int numsSize, int target) { // 基础边界处理 if (numsSize == 0) return -1; if (numsSize == 1) return nums[0] == target ? 0 : -1; // 调用独立函数找分段点 int polit = find_split_point(nums, numsSize); // 情况1：数组完全递增（无分段点）→ 直接全局二分 if (polit == -1) { return binary_search(nums, 0, numsSize - 1, numsSize, target); } // 情况2：找到分段点 → 按target和首元素的关系选区间 if (target == nums[0]) { return 0; // 首元素就是target，直接返回 } int left, right; if (nums[0] > target) { // target更小 → 在分段点右侧的递增区间查找 left = polit + 1; right = numsSize - 1; } else { // target更大 → 在分段点左侧的递增区间查找 left = 0; right = polit; } return binary_search(nums, left, right, numsSize, target); }