搜索旋转排序数组

不念不忘少年蓝@ 2022-01-21 09:41 238阅读 0赞

## 1、题目描述 ##

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

( 例如，数组 \[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

## 2、解法 ##

## 2.1 先找旋转点 ##

public int search(int[] nums, int target) { 
    		if(nums ==null || nums.length<1) { 
    			return -1;
    		}
    		
    		int right=nums.length-1, left=0, mid;
    		while (left<right) { 
    			mid = (left+right)/2;
    			if(nums[mid]>nums[right]) { 
    				left = mid+1;
    			}else { 
    				right = mid;
    			}
    		}
    		int split_k = left;
    		left=0;
    		right=nums.length-1;
    		if(target>= nums[split_k] && target<=nums[right]) { 
    			left = split_k;
    		}else { 
    			right = split_k;
    		}
    		while (left<=right) { 
    			mid=(left+right)/2;
    			if(nums[mid] == target) { 
    				return mid;
    			}else if(target>nums[mid]) { 
    				left = mid+1;
    			}else { 
    				right = mid-1;
    			}
    		}
    		return -1;
        }

发表评论取消回复

表情：

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

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

相关阅读

相关搜索旋转排序数组

[力扣][Link 1] 整数数组 `nums` 按升序排列，数组中的值互不相同。在传递给函数之前，`nums` 在预先未知的某个下标 `k`（`0 <= k < n

ゞ浴缸里的玫瑰/ 2024年03月26日 18:59/ 0 赞/ 63 阅读

相关【LeetCode 33】搜索旋转排序数组

题目描述假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 \[0,1,2,4,5,6,7\] 可能变为 \[4,5,6,7,0,1,2\] )。

﹏ヽ暗。殇╰゛Y/ 2022年12月04日 09:17/ 0 赞/ 198 阅读

相关 33. 搜索旋转排序数组

[https://leetcode-cn.com/problems/search-in-rotated-sorted-array/][https_leetcode-cn.com

刺骨的言语ヽ痛彻心扉/ 2022年09月09日 09:53/ 0 赞/ 186 阅读

相关 Leetcode 33. 搜索旋转排序数组

题目重述整数数组 nums 按升序排列，数组中的值互不相同。在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进

た入场券/ 2022年09月07日 01:22/ 0 赞/ 180 阅读

相关 33. 搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值互不相同。在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数

悠悠/ 2022年08月31日 07:17/ 0 赞/ 162 阅读

相关 [Leetcode][python]搜索旋转排序数组/搜索旋转排序数组 II

Search in Rotated Sorted Array 题目大意把一个严格升序的数组进行旋转，如\[0,1,2,3,4,5\]旋转3位成为\[3,4,5,0

蔚落/ 2022年06月09日 14:54/ 0 赞/ 242 阅读

相关 LeetCode——搜索旋转排序数组

题目：假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 `[0,1,2,4,5,6,7]` 可能变为 `[4,5,6,7,0,1,2]` )。搜

偏执的太偏执、/ 2022年05月16日 12:19/ 0 赞/ 204 阅读

相关【LeetCode】33. 搜索旋转排序数组

题目链接：[https://leetcode-cn.com/problems/search-in-rotated-sorted-array/description/][http

以你之姓@/ 2022年05月08日 05:44/ 0 赞/ 190 阅读

相关 LeetCode 搜索旋转排序数组

> 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 > > ( 例如，数组 `[0,1,2,4,5,6,7]` 可能变为 `[4,5,6,7,0,1,2]` )。 >

女爷i/ 2022年03月07日 11:06/ 0 赞/ 275 阅读

相关搜索旋转排序数组

1、题目描述假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 \[0,1,2,4,5,6,7\] 可能变为 \[4,5,6,7,0,1,2\]

不念不忘少年蓝@/ 2022年01月21日 09:41/ 0 赞/ 239 阅读