33-search-in-rotated-sorted-array.md

title	tags	grammar_cjkRuby
33-search-in-rotated-sorted-array	新建,模板,小书匠	true

problem

33-search-in-rotated-sorted-array

similiar problem

lint62 Search in Rotated Sorted Array

solution

    int search(vector<int>& nums, int target) {
        //先找到中间点;
        if (nums.empty())
            return -1;
        int i = 0, j = nums.size() - 1;
        if ( nums[i] > nums[j])
        {
            while ( i + 1 < j)
            {
                int k = i + (j - i) / 2;
                if (nums[k] > nums[0])
                    i = k;
                else
                    j = k;
            }
        }
        else
            i = j;
        if (target >= nums[0])//左边
        {
            return binSearch(nums, 0, i, target);
        }
        else//右边
        {
            return binSearch(nums, j, nums.size()-1, target);
        }
        
    }
    int binSearch(vector<int>& nums, int start, int end, int target)
    {
        if (start == end && nums[start] != target)
            return -1;
        int mid = start + (end - start) / 2;
        if (nums[mid] == target)
            return mid;
        if (nums[mid] < target)
            return binSearch(nums, mid + 1, end, target);
        else
            return binSearch(nums, start, mid, target);
    }

开头比较法

    int search(vector<int>& nums, int target) {
        //先找到中间点;
        if (nums.empty())
            return -1;
        int i = 0, j = nums.size() - 1;
        while ( i + 1 < j )
        {
            int k = i + (j - i) / 2;
            if ( target == nums[k])
                return k;
            if ( nums[i] < nums[k] )
            {
                if ( nums[i] <= target && nums[k] >= target)
                    j = k;
                else
                    i = k;
            }
            else
            {
                if (nums[k] <= target && nums[j] >= target)
                    i = k;
                else
                    j = k;
            }

        }
        if (nums[i] == target)
            return i;
        if (nums[j] == target)
            return j;
        return -1;
    }