198-旋转数组中的查找

分手后的思念是犯贱 2022-10-30 10:22 89阅读 0赞

**题目如下：**  
假设按照升序排序的数组在预先未知的某个点上进行了旋转。  
( 例如，数组 \[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

**解题思路：**

## 采用二分搜索的思想解决此问题 ##

**代码及注释如下：**

#include<stdio.h>
    int search(int *nums, int len,int target)
    {
        
    	//示例 ：[4,5,6,7,0,1,2] [8 9 1 2 3 4 5 6]
    	if (len == 0)
    		return -1;
    	int left = 0, right = len - 1;
    	while (left <= right)
    	{
        
    		int mid = (left + right) / 2;
    		if (nums[mid] == target)//匹配到，直接返回mid
    		{
        
    			return mid;
    		}
    		if (nums[left] <= nums[mid])//l到mid区间没有被旋转
    		{
        
    			//如果target在这个区间内
    			if (target >= nums[left] && target < nums[mid])
    			{
        
    				right = mid - 1;
    			}
    			else//target不在这个区间内
    			{
        
    				left = mid + 1;
    			}
    		} 
    		else//l到mid当中有旋转记录，例如：[8 9 1 2 3 4 5 6]
    		{
        
    			if (target < nums[left] && target > nums[mid])
    			{
        
    				left = mid + 1;
    			}
    			else
    			{
        
    				right = mid - 1;
    			}
    		}
    	}
    	return -1;
    }
    int main()
    {
        
    	int arr[]={
        4,5,6,7,0,1,2};
    	int len1=sizeof(arr)/sizeof(arr[0]);
    	printf("%d\n",search(arr,len1,0));
    	printf("%d\n",search(arr,len1,3));
    
    	return 0;
    }

**运行截图如下：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/451601738f01431abcd10bc962e44212.png