image.png
我的代碼:
class Solution {
public int search(int[] nums, int target) {
if (nums==null || nums.length ==0) return -1;
if (nums[0]==target) return 0;
if (nums[nums.length-1]==target) return nums.length-1;
int low = 0;
int high = nums.length-1;
while (low<high){
int mid = low + (high - low )/2;
if (target == nums[mid]) return mid;
if (nums[mid] > nums[high]){ //如mid 大過最右值, 則mid左部份為順序
//search if target is in this range
if (nums[0]<target && nums[mid]>=target){
high = mid-1;
}
else {
low = mid +1;
}
}
else { //if 如果mid小於最右值, 則,mid至high部份為 sorted,
if (nums[mid]<target && nums[high]>=target){ //這裡要包括當(dāng)nums[high] = target的情況
low = mid +1;
}
else {
high = mid-1;
}
}
}
int mid = low + (high - low )/2;
if (target == nums[mid]) return mid;
//只需要在上面while condition 中加入= 就可免卻這兩行多餘的代碼 while(low<=high){}
return -1;
}
}
思路: 如 nums[mid] > nums.length-1 , 則左半部份為sorted,
別人代碼:
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if not nums: return -1
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) / 2
if nums[mid] == target:
return mid
if nums[mid] < nums[right]:
if target > nums[mid] and target <= nums[right]:
left = mid + 1
else:
right = mid - 1
else:
if target < nums[mid] and target >= nums[left]:
right = mid - 1
else:
left = mid + 1
return -1
---------------------
版權(quán)聲明：本文為CSDN博主「負(fù)雪明燭」的原創(chuàng)文章致板，遵循CC 4.0 by-sa版權(quán)協(xié)議津辩，轉(zhuǎn)載請(qǐng)附上原文出處鏈接及本聲明几苍。
原文鏈接：https://blog.csdn.net/fuxuemingzhu/article/details/79534213
