My LeetCode: https://leetcode-cn.com/u/ituring/

My LeetCode source code [GitHub]: https://github.com/izhoujie/Algorithmcii

LeetCode 33. Search rotation sort array

subject

Let's say that the array sorted in ascending order is rotated at a pre-known point.

(for example, the array [0,1,2,4,5,6,7] may change to [4,5,6,7,0,1,2]).

Search a given target value. If the target value exists in the array, its index will be returned, otherwise - 1 will be returned.

You can assume that there are no duplicate elements in the array.

Your algorithm time complexity must be \ (\ Omicron\left(logn\right) \) level.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
 Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
 Output: - 1

Source: LeetCode
Link: https://leetcode-cn.com/problems/search-in-rotated-sorted-array
Copyright belongs to the network. For commercial reprint, please contact the official authorization. For non-commercial reprint, please indicate the source.

Solutions to problems

The time complexity of the algorithm is required to be \ (\ Omicron\left(logn\right)), so it must be solved by binary search;

Idea 1-binary search

The premise of binary search is array order, the current array is local order, so we need to determine the ordered interval first and then use binary search;
The general method is the same, but the ordered interval needs to be determined when judging the size;
Step:

1. left, right, middle position mid;
2. To determine the ordered interval, it is currently divided into [left, mid] and [mid, right], one of which must be the ordered increasing interval. The judgment method is to see whether the target is in the middle of the interval;
3. In the ordered interval, the conventional binary search algorithm logic is used;

Algorithm complexity:

• Time complexity: ${\ color{Magenta}{\Omicron\left(logn\right)}}}$
• Spatial complexity: ${\ color{Magenta}{\Omicron\left(1\right)}}$

Algorithm source code example

package leetcode;

/**
 * @author ZhouJie
 * @date 2020 10:22:10 PM, January 17, 2010 
 * @Description: 33. Search rotation sort array
 *
 */
public class LeetCode_0033 {
	public static void main(String[] args) {
		int test1[] = { 4, 5, 6, 7, 0, 1, 2 };
		int test2[] = { 1, 3 };
		int test3[] = { 4, 5, 6, 7, 0, 1, 2 };
		System.out.println(new Solution_0033().search_1(test1, 0));
		System.out.println(new Solution_0033().search_1(test2, 3));
		System.out.println(new Solution_0033().search_1(test3, 8));
	}
}

class Solution_0033 {
	/**
	 * @author: ZhouJie
	 * @date: 2020 9:39:47 PM, February 4, 2004 
	 * @param: @param nums
	 * @param: @param target
	 * @param: @return
	 * @return: int
	 * @Description: 1-Not optimized
	 *
	 */
	public int search_1(int[] nums, int target) {
		if (nums == null) {
			return -1;
		}
		int i = 0, j = nums.length - 1, k;
		while (i <= j) {
			k = (i + j) / 2;
			if (i == j && nums[k] != target) {
				return -1;
			}
			if (nums[k] == target) {
				return k;
			} else if (nums[i] > nums[k] && nums[k] < nums[j]) {
				if (target > nums[k] && target <= nums[j]) {
					i = k + 1;
				} else {
					j = k - 1;
				}
			} else if (nums[i] < nums[k] && nums[k] > nums[j]) {
				if (target >= nums[i] && target < nums[k]) {
					j = k - 1;
				} else {
					i = k + 1;
				}
			} else if (nums[i] <= nums[k] && nums[k] < nums[j]) {
				if (target < nums[k]) {
					j = k - 1;
				} else {
					i = k + 1;
				}
			} else if (target > nums[j]) {
				j = k - 1;
			} else {
				i = k + 1;
			}
		}
		return -1;
	}

	/**
	 * @author ZhouJie
	 * @date 2020 12:13:34 am, January 19, 2010 
	 * @Description: TODO(Method brief) 
	 * @return int 
	 * @UpdateUser-UpdateDate:[ZhouJie]-[2020 12:13:34 am, January 19, 2015]  
	 * @UpdateRemark:2-Thought: the key is to find the ordered interval, and each judgment is only carried out in the ordered interval, which is relatively clear;
	 *
	 */
	public int search_2(int[] nums, int target) {
		if (nums == null) {
			return -1;
		}
		int left = 0, right = nums.length - 1;
		int mid;
		while (left <= right) {
			mid = left + (right - left) / 2;
			if (nums[mid] == target) {
				return mid;
				// If nums [mid] < nums [right], it means that the right half is increasing in order. Here, the left half cannot be priori, because mid may be equal to left
			} else if (nums[mid] < nums[right]) {
				// If the target value is within the right ordered range
				if (target > nums[mid] && target <= nums[right]) {
					left = mid + 1;
					// The target is on the left
				} else {
					right = mid - 1;
				}
				// If the right half is disordered, it means that the left half is in order, and judgment is made on the left half
			} else {
				// If the target value is in the ordered interval of the left half
				if (target >= nums[left] && target < nums[mid]) {
					right = mid - 1;
				} else {
					left = mid + 1;
				}
			}
		}
		return -1;
	}
}