Leetcode题解（十二）

33、Search in Rotated Sorted Array

题目

这道题目如果没有其他要求，直接遍历一遍就可以知道答案，但是，题目给出了是排序了数组，但是数组有可能经过了旋转得到，其解题思路仍然是二分查找，只不过在处理的时候需要添加一下逻辑处理；

在做逻辑判断的时候，主要判断的是target可能位于middle的坐标还是右边，这样才能确定应该执行first = middle+1还是second = middle - 1；

旋转后的数组可以分为两部分，前一部分是数组递增部分，如[4,5,6,7]，后一部分是[0,1,2]

代码如下：

 1 class Solution {
 2 public:
 3     int search(vector<int>& nums, int target) {
 4         int first,second,middle;
 5         first = 0;
 6         second = nums.size() - 1;
 7 
 8         while (first <= second)
 9         {
10             middle = (first + second)/2;
11             if(target == nums[middle])
12                 return middle;
13             if(nums[middle] >= nums[first] && nums[middle] >= nums[second])//middle位于前一部分并且first在前一部分，second在后一部分
14             {
15                 if(target >= nums[first] && target > nums[middle])//middle可能位于前一部分，并且位于middle右边，所以first=middle+1
16                     first = middle+1;
17                 else if(target >= nums[first] && target < nums[middle])//middle可能位于前一部分，并且位于middle的左边
18                     second = middle-1;
19                 else 
20                     first = middle+1;
21             }
22             else if(nums[middle] <= nums[first] && nums[middle] <= nums[second])//middle位于后一部分，并且first位于前一部分，second位于后一部分
23             {
24                 if(target <= nums[second] && target < nums[middle])
25                     second = middle-1;
26                 else if(target <= nums[second] && target > nums[middle])
27                     first = middle+1;
28                 else
29                     second = middle-1;
30             }
31             else //first和second位于同一部分，就退化为普通的二分查找了
32             {
33                 if(target > nums[middle])
34                     first = middle+1;
35                 else
36                     second = middle-1;
37             }
38         }
39 
40         return -1;
41 
42 
43     }
44 };

--------------------------------------------------------------------------------------------分割线--------------------------------------------------------------------------------

34、Search for a Range

题目

这道题目是二分法的具体应用，直接上代码;

 1 class Solution {
 2 public:
 3     vector<int> searchRange(vector<int>& nums, int target) {
 4         int first,second,middle;
 5         const int size = nums.size();
 6         vector<int> res;
 7 
 8         first = 0;
 9         second = size - 1;
10 
11         while(first <= second)
12         {
13             middle = (first + second)/2;
14             if(target == nums[middle])
15                 break;
16             else
17             {
18                 if(target > nums[middle])
19                     first = middle+1;
20                 else
21                     second = middle-1;
22             }
23         }
24         int t;
25         if(first <= second)
26         {
27             t = middle;
28             while(target == nums[t]&&t>=0)
29                 t--;
30             t++;
31             res.push_back(t);
32             t=middle;
33             while(target == nums[t]&&t<size)
34                 t++;
35             t--;
36             res.push_back(t);
37 
38         }
39         else
40         {
41             res.push_back(-1);
42             res.push_back(-1);
43         }
44         return res;
45     }
46 };

-----------------------------------------------------------------------------------分割线-----------------------------------------------------------------------------------------

35、Search Insert Position

题目

二分查找的应用，直接代码：

 1 class Solution {
 2 public:
 3     int searchInsert(vector<int>& nums, int target) {
 4         const int size = nums.size();
 5         if(0 == size)
 6             return 0;
 7 
 8         int first,second,middle;
 9         first = 0;
10         second = size - 1;
11 
12         while(first < second)//注意没有用<=
13         {
14             middle = (first + second)/2;
15             if (target == nums[middle]) 
16             {
17                 return middle;
18             }
19             else if (target > nums[middle])
20             {
21                 first = middle+1;
22             }
23             else
24                 second = middle-1;
25         }
26 
27         if(target > nums[first])
28             return first+1;
29         else
30             return first;
31 
32     }
33 };