leetcode - --------------------- Search for Rotary Sort Array

This problem is actually dichotomy search, so it is relatively simple, but my code is not good.

My idea is to first find the rotating node by dichotomy, and then rotate on the left or right side of the node.

The first step of binary search, my code has done a lot of unnecessary operations;

My first step is to find out whether the left side is smaller than the right, and if not, return to the rotating node.

class Solution {
public:

	array<int, 3> find_point(vector<int>&nums, int lo, int hi)
	{
		if (lo == hi)  return array<int, 3>{lo, lo, 0};
		int mi = lo + (hi - lo) / 2;
		array<int, 3> left = find_point(nums, lo, mi);
		array<int, 3> right = find_point(nums, mi + 1, hi);
		if (left[2] == 1) return array<int, 3>{left[0], left[1], 1};
		if (right[2] == 1) return array<int, 3>{right[0], right[1], 1};
		if (nums[left[1]] < nums[right[0]])    return array<int, 3>{left[0], right[1], 0};
		else return array<int, 3>{left[1], left[1], 1};
	}


	int find(vector<int>&nums, int lo, int hi, int target)
	{
		if (lo == hi) {
			if (target == nums[lo])    return lo;
			else return -1;
		}
		int mi = lo + (hi - lo) / 2;
		if (target <= nums[mi]&&target>=nums[lo]) return find(nums, lo, mi, target);
		else return find(nums, mi + 1, hi, target);
	}


	int search(vector<int>& nums, int target) {
        if(nums.empty()) return -1;
		array<int, 3> cut_point = find_point(nums, 0, nums.size() - 1);
        if (cut_point[2] == 0)	return find(nums, 0, nums.size() - 1, target);
		if (target <= nums[cut_point[0]]&&target>=nums[0]) return find(nums, 0, cut_point[0], target);
		else return find(nums, cut_point[0] + 1, nums.size() - 1, target);
	}
};

So I looked at other people's alternative solutions: I don't explain here; I paste others'explanations directly. I think when he searches directly, he decides whether the left side is an ascending array or not. If not, he says that there are rotating nodes in it, and then he does it by comparing whether the target is inside or not. Reduce the interval to find, so that one step in place:

Notice that the original array is a restricted ordered array (all ascending arrays except for a sudden drop at some point)

If nums[0] <= nums[i], then nums[0] to nums[i] are ordered arrays, then when nums[0] <= target <= nums[i], we should look in the range of 0-i0_i;

If nums[i] < nums[0], then a drop (rotation) occurs at a point in the 0-i0_i interval, then the interval from I+1I+1 to the last number is an ordered array, and all the numbers are less than nums[0] and larger than nums[i], when target does not belong to nums[0] to nums[i] (target <= nums[i] < nums[0] or nums[i] < nums[0] <= target), we should look in the 0-i0_i interval.
These three situations can be summarized as follows:

    nums[0] <= target <= nums[i]
               target <= nums[i] < nums[0]
                         nums[i] < nums[0] <= target
So we make three judgments:

(nums [0] <= target), (target <= nums [i], (nums [i] < nums [0]), and now we want to know which of these three items is true (obviously these three items can't be true or false (because they may already cover all situations).

So now we just need to distinguish whether two of the three items are true or only one is true.

The above results can be easily obtained by using XOR operation (two are true-time XOR or the results are false, one is true-time XOR or the results are true, which can be verified by drawing truth table).

Then we continue to do the interval where the small target may be located until low==high through binary search. If nums[low]==target, then we find it. If not, it means that there is no such item in the array.

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int lo = 0, hi = nums.size() - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if ((nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid]))
                lo = mid + 1;
            else
                hi = mid;
        }
        return lo == hi && nums[lo] == target ? lo : -1;
    }
};

 

Tags: less

Posted on Wed, 04 Sep 2019 05:06:15 -0700 by lucym