[LeetCode] 33. Search in Rotated Sorted Array

轉自LeetCode

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.

<Solution>

這題是要在 rotate 過的 sorted list 裡面找值，且 rotate 的位置不知道

因為可能有 rotate 過，所以會有一個區段就不是 sorted 了

那因為題目有說，list 裡面不會有重複的值，這個讓難度有降低

思考的情況有幾種

• 如果沒有 rotate 過，第一個元素一定小於最後一個元素，因為是 sorted list，反之則有rotate過

• 如果沒有 rotate 過，那 target < 第一個元素，或是 target > 最後一個元素，就返回 -1，因為一定不在 list 裡

• 如果有 rotate 過，那 target < 第一個元素且 target > 最後一個元素，就返回 -1，因為一定不在 list 裡

• 如果上述情況都不符合，就要開始找

• 沒有 rotated，可以歷遍找，也可以用 binary search 找，都會過，用 binary search 會快一點

• 有 rotated，先看 target 是在左半還是右半，大於等於第一個元素，在左半，反之在右半

• 在左半，從第一個元素找起，遇到下一個元素比目前小，代表找不到了

• 在右半，從最後一個元素找起，遇到下一個元素比目前大，代表找不到了

code 如下

	class Solution {
	public:
	int search(vector<int>& nums, int target) {
	if(nums.empty()) {
	return -1;
	}
	else if(nums.size() == 1) {
	return (nums[0] == target) ? 0 : -1;
	}
	//> check list is rotated or not
	bool isRotated = (nums.front() > nums.back()) ? true : false;
	//> absolutly not in the list
	if(isRotated) {
	if(target > nums.back() && target < nums.front()) {
	return -1;
	}
	}
	else {
	if(target < nums.front() || target > nums.back()) {
	return -1;
	}
	}
	//> need to search
	if(isRotated) { //> rotated
	if(target >= nums.front()) { //> target is in the left half
	for(int i = 0; i < nums.size(); i++) {
	if(target == nums[i]) {
	return i;
	}
	else if(nums[i+1] < nums[i]) {
	//> reach left half end
	return -1;
	}
	}
	}
	else { //> target is in the right half
	for(int i = nums.size() - 1; i >= 0; i--) {
	if(target == nums[i]) {
	return i;
	}
	else if(nums[i-1] > nums[i]) {
	//> reach right half end
	return -1;
	}
	}
	}
	}
	else { //> not rotated
	//> use binary search
	int left = 0, right = nums.size() - 1;
	while(left <= right) {
	int mid = (left + right) / 2;
	if(nums[mid] == target) {
	return mid;
	}
	else if(target > nums[mid]) {
	left = mid + 1;
	}
	else {
	right = mid-1;
	}
	}
	}
	return -1;
	}
	};

view raw searchInRotatedList.cpp hosted with ❤ by GitHub

也可以直接用 binary search 來找

kotlin

	class Solution {
	fun search(nums: IntArray, target: Int): Int {
	var left = 0
	var right = nums.lastIndex
	var mid: Int
	while(left <= right) {
	mid = left + (right - left) / 2
	when {
	nums[mid] == target -> return mid
	nums[mid] >= nums[left] -> {
	if(nums[left] <= target && nums[mid] > target) {
	right = mid - 1
	} else {
	left = mid + 1
	}
	}
	else -> {
	if(nums[mid] < target && nums[right] >= target) {
	left = mid + 1
	} else {
	right = mid - 1
	}
	}
	}
	}
	return -1
	}
	}

view raw search_in_rotated_sorted_array.kt hosted with ❤ by GitHub