LeetCode之Search in Rotated Sorted Array

喜欢ヅ旅行 2022-08-05 12:17 133阅读 0赞

题目：Suppose a sorted array is rotated at some pivot unknown to you beforehand.  
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).  
You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

分析：已经排序的数组从某个点翻转了，假设数组中没有重复的元素，顺序查找当然可以，但是要利用有已有的排序。那么只有在二分查找的基础上下功夫了。具体思路是，数组中的左右的数组必有一个有序，那么我们就只处理有序的那一部分，如果目标元素在这个有序的部分，那么就把范围定位到这部分，直接二分查找即可。如果不在，继续缩小范围，直到将元素定位到有序的那部分。

代码：

class Solution{
    public:
    	int search(int A[], int n, int target) {
    		int first =0 ;int last = n;
    		while(first != last){
    			int mid = (first + last)/2;
    			if (A[mid] == target){
    				return mid;
    			}
    			if (A[first] <= A[mid]){ //first到mid之间元素内有序，那么就在该段内尝试查找
    				//判断target是否在范围之内
    				if (A[first]<=target && target < A[mid]){
    					last = mid;
    				}else{
    					first = mid + 1;
    				}
    			}else{ //first到mid之间元素无序,那么这时后半部分有序，尝试查找。
    				//判断target是否在范围之内
    				if (A[mid] < target && target <= A[last - 1]){
    					first = mid + 1;
    				}else{
    					last = mid;
    				}
    			}
    		}
    		return -1;
    	}
    };

自我感觉这题优点难。

发表评论取消回复

表情：

评论列表（有 0 条评论，133人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode - Medium - 33. Search in Rotated Sorted Array

Topic Array Binary Search Description [https://leetcode.com/problems/search

红太狼/ 2023年01月04日 11:53/ 0 赞/ 154 阅读

相关 LeetCode81——Search in Rotated Sorted Array II

LeetCode81——Search in Rotated Sorted Array II 加入重复数据的Search in Rotated Sorted Array

小灰灰/ 2022年08月20日 02:30/ 0 赞/ 26 阅读

相关 Search in Rotated Sorted Array--LeetCode

题目： Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e.

红太狼/ 2022年08月05日 13:14/ 0 赞/ 20 阅读

相关 LeetCode之Search in Rotated Sorted Array二

题目：Follow up for ”Search in Rotated Sorted Array”: What if duplicates are allowed? Wou

古城微笑少年丶/ 2022年08月05日 12:17/ 0 赞/ 147 阅读

相关 LeetCode之Search in Rotated Sorted Array

题目：Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0

喜欢ヅ旅行/ 2022年08月05日 12:17/ 0 赞/ 134 阅读

相关 leetcode 33. Search in Rotated Sorted Array 二分查找

Suppose an array sorted in ascending order is rotated at some pivot unknown to you befor

痛定思痛。/ 2022年06月09日 09:42/ 0 赞/ 124 阅读

相关 33. Search in Rotated Sorted Array

描述： Suppose an array sorted in ascending order is rotated at some pivot unknown to you

深藏阁楼爱情的钟/ 2022年06月02日 01:26/ 0 赞/ 159 阅读

相关 python -- leetcode ---- 81.Search in Rotated Sorted Array II

\-81.Search in Rotated Sorted Array II 给定一个list,是由一个有序数组在某一枢纽处旋转得到的,并且其中可能含有重复元素,要求判断

红太狼/ 2022年05月13日 13:44/ 0 赞/ 130 阅读

相关 81. Search in Rotated Sorted Array II

Suppose an array sorted in ascending order is rotated at some pivot unknown to you befor

谁借莪１个温暖的怀抱￠/ 2022年03月07日 14:45/ 0 赞/ 190 阅读

相关 leetcode--Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array": What if duplicates are allowed? Would

Bertha 。/ 2021年10月16日 01:12/ 0 赞/ 228 阅读