leetcode 33. Search in Rotated Sorted Array 二分查找

痛定思痛。 2022-06-09 09:42 110阅读 0赞

Suppose an array sorted in ascending order 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.

就是在一个旋转后的数组中寻找target数据。

很明显，最简单的方法就是遍历一次，不过题目的意思明显不是要求这么做的，主要考察的还是使用二分查找，所以这里使用二分查找来做。

代码如下：

public class Solution {
        public int search(int[] nums, int target) 
        {
            if(nums==null || nums.length<=0)
                return -1;
    
            /* 下面的属于遍历求解，很明显，不是这么做
            int res=-1;
            for(int i=0;i<nums.length;i++)
            {
                if(nums[i]==target)
                {
                    res=i;
                    break;
                }
            }
            return res;*/
    
            //寻找最小值的index
            int minIndex=0;   
            for(int i=1;i<nums.length;i++)
                minIndex=(nums[minIndex]>=nums[i])? i : minIndex;
    
            int res=-1;
            //确认是从小到大的排列
            if(minIndex==0)
                res=binarySearch(nums,0,nums.length-1,target);
            else
            {
                //分成两部分做二分查找
                int t=binarySearch(nums,0,minIndex-1,target);
                int tt=binarySearch(nums, minIndex, nums.length-1,target);
                if(t!=-1)
                    res=t;
                if(tt!=-1)
                    res=tt;
            }
            return res;
        }
    
        private int binarySearch(int[] nums, int start, int end,int target)
        {
            if(start>end)
                return -1;
            else if(start==end)
            {
                if(nums[start]==target)
                    return start;
                else
                    return -1;
            }else
            {
                int mid=(start+end)/2;
                if(nums[mid] < target)
                    return binarySearch(nums, mid+1, end, target);
                else
                    return binarySearch(nums, start, mid, target);
            }
        }
    }

C++的做法就是直接遍历

代码如下：

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    class Solution 
    {
    public:
        int search(vector<int>& nums, int target) 
        {
            for (int i = 0; i < nums.size(); i++)
            {
                if (nums[i] == target)
                    return i;
            }
            return -1;
        }
    };

这道题其实考察的是**二分查找**

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    #include <array>
    using namespace std;
    
    
    
    class Solution 
    {
    public:
        int search(vector<int>& a, int target) 
        {
            int left = 0, right = a.size() - 1;
            while (left <= right)
            {
                int mid = (left + right) / 2;
                if (a[mid] == target)
                    return mid;
                else if (a[mid] < a[right])
                {
                    if (target > a[mid] && target <= a[right])
                        left = mid + 1;
                    else
                        right = mid - 1;
                }
                else
                {
                    if (target >= a[left] && target < a[mid])
                        right = mid - 1;
                    else
                        left = mid + 1;
                }
            }
            return -1;
        }
    };