原题
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [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
解法
思想
二分查找，需要注意、区分一些情况。
代码
class Solution {
public int search(int[] nums, int target) {
if(nums.length == 0) return -1;
int head = nums[0];
if(target == head) return 0;
int start = 0;
int end = nums.length-1;
int mid = 0;
while(start<=end){
mid = start + (end-start)/2;
if(nums[mid] == target) return mid;
if(nums[mid]>target){//mid比target大
if(target>head){//target在左边
if(nums[mid]>=head) end = mid-1;//mid在左边
else start = mid+1;
}else{//target在右边
if(nums[mid]>=head) start = mid+1;//mid在左边
else end = mid-1;
}
}else if(nums[mid]<target){//mid比target小
if(target>head){//target在左边
if(nums[mid]>=head) start = mid+1;//mid在左边
else end = mid-1;
}else{//target在右边
start = mid+1;
}
}
}
return -1;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode33-%e6%90%9c%e7%b4%a2%e6%97%8b%e8%bd%ac%e6%8e%92%e5%ba%8f%e6%95%b0%e7%bb%84/
相关推荐
-
leetcode119-杨辉三角II
原题 给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。在杨辉三角中，每个数是它左上方和右上方的数的和。 示例: 输入: 3 输出: [1,3,3,1] 进阶： ...
-
leetcode160-相交链表
原题 编写一个程序，找到两个单链表相交的起始节点。 如下面的两个链表： 在节点 c1 开始相交。 示例 1： 输入： intersectVal = 8, listA = [4,1,...
-
leetcode1114-按序打印
原题 我们提供了一个类： public class Foo { public void one() { print("one"); } public void two() ...
-
leetcode341-扁平化嵌套列表迭代器
原题 给定一个嵌套的整型列表。设计一个迭代器，使其能够遍历这个整型列表中的所有整数。 列表中的项或者为一个整数，或者是另一个列表。 示例1： 输入: [[1,1],2,[1,1]]...
-
leetcode494-目标和
原题 给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。...
-
leetcode278-第一个错误的版本
原题 你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。 假...
-
leetcode1071-字符串的最大公因子
原题 对于字符串 S 和 T，只有在 S = T + ... + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。 返回最长字符串 X，要求满足 X 能除尽 ...
-
leetcode209-长度最小的子数组
原题 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。 示例: 输入: s = ...
-
leetcode9-回文数
原题 判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。 示例1: 输入： 121 输出： true 示例2: 输入： -121 输出： fa...
-
leetcode590-N叉树的后序遍历
原题 给定一个 N 叉树，返回其节点值的后序遍历。 例如，给定一个 3叉树 : 返回其前序遍历: [5,6,3,2,4,1]. 说明: 递归法很简单，你可以使用迭代法完成此题吗? ...
