Leecode热题100--二分查找---33：搜索旋转排序矩阵

题目：
整数数组 nums 按升序排列，数组中的值 互不相同 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

思路：
此处采用容易理解的两次二分查找法，确定target位置。
第一次先找到旋转点用一次二分
第二次确定target在哪个区间之后再二分搜索

class Solution
{
public:
	int search(vector<int>& nums,int target)
	{
		int L = 0, R = nums.size() - 1;
		// [)区间
		// 最后一个判断的是最小值，即旋转点
		// 第一次二分查找，确定最小值索引
		while(L < R)
		{
			int mid = L + (R - L)/2;
			if (nums[mid] <= nums[R])
			{
				R = mid;
			}
			else
			{
				L = mid + 1;
			}
		}
		// 上述循环结束， R=L 都会指向最小值的索引

		// 确定target在哪个区间，更新左区间或右区间值
		int left, right;
		if(target >= nums[0] && R != 0 && target <= nums[R-1])
		{
			left = 0;
			right = R;
		}
		else
		{
			left = R;
			right = nums.size() - 1;
		}

		// 第二次二分查找，确定target索引
		while(left <= right)
		{
			int mid = left + (right-left)/2;
			if(nums[mid] == target)  return mid;
			else if(nums[mid] < target)
			{
				left = mid + 1;
			}
			else
			{
				right = mid - 1;
			}
		}
		return -1;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

Leecode—153：寻找旋转矩阵中的最小值
思路同上，取第一次二分查找即可。

class Solution {
public:
    int findMin(vector<int>& nums) {
        int L =0, R = nums.size()-1;
        // [)区间
		// 最后一个判断的是最小值，即旋转点
		// 一次二分查找，确定最小值索引
        while(L < R)
        {
            int mid = L + (R-L)/2;
            if(nums[mid] <= nums[R])
            {
                R = mid;
            }
            else
            {
                L = mid + 1;
            }
        }
        // 返回值L=R都是最小值索引
        return nums[L];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23