033 搜索旋转排序数组

题目

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

示例 3:

输入: nums = [5,1,3], target = 5
输出: 0

示例 4:

输入: nums = [4,5,6,7,8,1,2,3], target = 8
输出: 0

示例 5:

输入: nums = [3,1], target = 1
输出: 1

实现

第一种:利用二分法

  • 状态:通过
  • 196 / 196 个通过测试用例
  • 执行用时: 128 ms, 在所有 C# 提交中击败了 97.17% 的用户
  • 内存消耗: 23.8 MB, 在所有 C# 提交中击败了 12.00% 的用户
public class Solution 
{
    public int Search(int[] nums, int target) 
    {
        int i = 0, j = nums.Length - 1;
        while (i <= j)
        {
            int mid = (i + j) / 2;
            if (nums[mid] == target)
                return mid;

            if (nums[mid] >= nums[i])
            {
                //左半部分有序
                if (target > nums[mid])
                {
                    i = mid + 1;
                }
                else
                {
                    if (target == nums[i])
                        return i;

                    if (target > nums[i])
                        j = mid - 1;
                    else
                        i = mid + 1;
                }
            }
            else
            {
                if (target < nums[mid])
                {
                    j = mid - 1;
                }
                else
                {
                    if (target == nums[j])
                        return j;
                    if (target < nums[j])
                        i = mid + 1;
                    else
                        j = mid - 1;
                }
            }
        }
        return -1;        
    }
}
浙ICP备19012682号