1巡通、題目鏈接
https://leetcode.com/problems/search-in-rotated-sorted-array/
2内边、解題思路
剛開始看這道題的時候，沒注意看最后的要求，感覺很傻逼的一道題闰渔，直接遍歷數(shù)組暮现，然后判斷目標值是否和數(shù)組中的值相等还绘，然后返回下標，不存在就返回-1栖袋，后面才發(fā)現(xiàn)題目要求在時間復雜度在O(log n)級別的拍顷，而且題目是說給你一個排序的數(shù)組，但是這個排序的數(shù)組發(fā)生了一次意外塘幅，被旋轉(zhuǎn)了一次昔案，由此我們想到了二分查找算法，但是這是一個變種的二分查找电媳，需要根據(jù)實際情況來分多種情況考慮踏揣，由于只發(fā)生了一次旋轉(zhuǎn)（按照數(shù)組中的某個值進行旋轉(zhuǎn)，也就是換位置）匾乓，我們可以認定當我們把數(shù)組一分為二的時候至少有一半是有序的捞稿，另一半可能有序，詳細看我在下列代碼中的分析拼缝。
3娱局、代碼
- Java：
public static int search(int[] nums, int target) {
if (null == nums || nums.length == 0 || (nums.length == 1 && target != nums[0])) {
return -1;
}
if (nums.length == 1) {
return 0;
}
int left = 0;
int right = nums.length - 1;
while (left < right) {
int middle = (left + right) / 2;
if (nums[left] == target) {
return left;
}
if (nums[middle] == target) {
return middle;
}
if (nums[right] == target) {
return right;
}
if (nums[left] < nums[middle]) { //左邊是有序的
if (nums[middle] > target && nums[left] < target) {
//目標值在有序排列的左邊
right = middle - 1;
} else {
//目標值在無序排列的右邊
left = middle + 1;
}
} else { //右邊是有序的
//nums[middle] < nums[left]
if (nums[middle] < target && nums[right] > target) {
//目標值在有序排列的右邊
left = middle + 1;
} else {
//目標值在無序排列的左邊
right = middle - 1;
}
}
}
return -1;
}
- Python
def search(self, nums, target):
if nums is None or len(nums) == 0 or (len(nums) == 1 and nums[0] != target):
return -1
if len(nums) == 1 and nums[0] == target:
return 0
left = 0
right = len(nums) - 1
while left < right:
middle = (left + right) / 2
if nums[left] == target:
return left
if nums[middle] == target:
return middle
if nums[right] == target:
return right
if nums[left] < nums[middle]:
if nums[middle] > target > nums[left]:
right = middle - 1
else:
left = middle + 1
else:
if nums[middle] < target < nums[right]:
left = middle + 1
else:
right = middle - 1
return -1
- JavaScript
var search = function (nums, target) {
if (undefined == nums || null == nums
|| nums.length == 0 || (nums.length == 1 && nums[0] != target)) {
return -1
}
if (nums.length == 1 && nums[0] == target) {
return 0
}
let left = 0
let right = nums.length - 1
while (left < right) {
let middle = parseInt((left + right) / 2)
if (nums[left] == target) {
return left
} else if (nums[middle] == target) {
return middle
} else if (nums[right] == target) {
return right
}
if (nums[left] < nums[middle]) {
if (nums[middle] > target && nums[left] < target) {
right = middle - 1
} else {
left = middle + 1
}
} else {
if (nums[middle] < target && target < nums[right]) {
left = middle + 1
} else {
right = middle - 1
}
}
}
return -1
};
