Share my solution with interval decomposision


  • 0
    O
    class Solution {
    public:
    
        int index = -1;
        
        bool check(int start, int end, int target) {
            if (end > start) {
                return (target >= start) and (target <= end);
            } else {
                return target >= max(start, end) or target <= min(start, end);
            }
        }
    
        void f(int start, int end, int target, const vector<int> &x) {
            if (index != -1) return;
            if (end - start <= 4) {
                for (int i = start; i <= end; i++) {
                    if (x[i] == target) {
                        index = i;
                        break;
                    }
                }
            } else {
                int mid = start + (end - start) / 2;
                if (check(x[start], x[mid], target)) f(start, mid, target, x);
                if (check(x[mid + 1], x[end], target)) f(mid + 1, end, target, x);
            }
        }
        
        int search(vector<int>& nums, int target) {
            f(0, nums.size() - 1, target, nums);
            return index;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.