leetcode33：搜索旋转排序数组

题目链接

leetcode

题目描述

整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如，[0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2]。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标；否则，返回 -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;
}

/*
    二分法
    本质：分段性，而不是单调性

    时间复杂度：O(logn)
        其中 n 为 nums 数组的大小。
        二分查找，时间复杂度 O(logn)。
    时间复杂度：O(1)
        常数级别的空间存放变量。
*/
class Solution_0 {
public:
    int search(vector<int>& nums, int target) {
        if (nums.empty()) {
            return -1;
        }

        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (nums[mid] >= nums[0]) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        // target 确认在哪一段
        if (target >= nums[0]) {
            l = 0;
        } else {
            l = r + 1, r = nums.size() - 1;
        }

        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        // 当数组只有一个元素时，二分没有执行（l+1 会越界，r = length-1 不会越界）
        if (nums[r] == target) {
            return r;
        }
        return -1;
    }
};

/*
    思路同上
*/
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.empty()) {
            return -1;
        }

        int l = 0, r = nums.size() - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                return mid; // 找到目标值，返回索引
            }
            if (nums[mid] >= nums[l]) {
                // 左半部分有序
                if (nums[l] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                // 右半部分有序
                if (nums[mid] < target && target <= nums[r]) {
                    l = mid + 1;
                } else {
                    r = mid -1;
                }
            }
        }
        return -1;
    }
};

int main() {
    Solution solution;
    vector<int> nums = {4, 5, 6, 7, 0, 1, 2};
    printArray(nums);
    int target = 0;
    int result = solution.search(nums, target);
    cout << "Index of target " << target << " is: " << (result == -1 ? "Not Found" : to_string(result)) << endl;
  
    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
   二分查找：
       由于数组是旋转过的排序数组，数组被分为两部分，至少有一部分是有序的。
       利用这一特性，通过二分查找高效地定位目标值。
   判断有序部分：
        在每次迭代中，计算中间位置 mid。比较 nums[mid] 和 nums[left]：
        如果 nums[mid] >= nums[left]，说明左半部分是有序的。
        否则，右半部分是有序的。
   缩小搜索范围：
       如果目标值在有序部分内，将搜索范围缩小到该部分。
       否则，将搜索范围缩小到另一部分。
   返回结果：
       如果找到目标值，返回其索引。
       如果循环结束仍未找到目标值，返回 -1。

   时间复杂度：O(logn)
       二分查找：每次迭代将搜索范围缩小一半，因此时间复杂度为 O(logn)，其中 n 是数组的长度。
   空间复杂度：O(1)
       常数空间：使用了两个指针 left 和 right，空间复杂度为 O(1)。
*/
// search 在旋转排序数组中查找目标值的索引
func search(nums []int, target int) int {
    if len(nums) == 0 {
        return -1
    }

    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right - left) / 2
        if nums[mid] == target {
            return mid
        }
        if nums[mid] >= nums[left] { // 左半部分有序
            if nums[left] <= target && target < nums[mid] {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else {  // 右半部分有序
            if nums[mid] < target && target <= nums[right] {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
    }
    return -1
}

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

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