二分查找（一）

发表于   |   分类于   |     |  

数据结构中二分查找问题总结归纳。

Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array.LeetCode

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
/**
Example 1:
Input: [1,3,5,6], 5
Output: 2
Example 2:
Input: [1,3,5,6], 2
Output: 1
Example 3:
Input: [1,3,5,6], 7
Output: 4
Example 4:
Input: [1,3,5,6], 0
Output: 0
*/
int searchInsert(vector<int>& nums, int target) 
{
    int size = nums.size();
    int left = 0, mid = 0, right = size - 1;
    while(left <= right)
    {
        mid = (left + right) / 2;
        if(nums[mid] == target)
            return mid;
        else if(nums[mid] > target)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return left;        //没找到的情况下插入位置应该为left
}

Search for a Range

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm’s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4]. LeetCode

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
/*********二分法查找，找到目标值后前后搜索边界**********/
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int size = nums.size();
        if(size < 1 || target < nums[0] || target > nums[size - 1])
            return vector<int>({ -1, -1 });
        int left = 0, mid = 0, right = size - 1;
        vector<int> result;
        while(left <= right)
        {
            mid = (left + right) / 2;
            if(nums[mid] == target)
            {
                int j = mid - 1;
                while(j >= 0 && nums[j] == target)    j--;
                result.push_back(j + 1);
                j = mid + 1;
                while(j < size && nums[j] == target)    j++;
                result.push_back(j - 1);
                return result;
            }
            else if(nums[mid] > target)
            {
                right = mid - 1;
            }
            else 
            {
                left = mid + 1;
            }
        }
        return vector<int>({-1, -1});
    }
};

Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
For example, Consider the following matrix:
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target = 3, return true.LeetCode

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**
二分法查找，首先利用二分法定位目标值位于哪一行，然后在该行再次利用二分法查找
*/
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty() || matrix[0].empty())
            return false;
        int m = matrix.size(), n = matrix[0].size();
        int left = 0, right = m - 1, mid = 0, row = 0;
        while(left <= right)
        {
            mid = (left + right) / 2;
            //如果目标值在上一行的尾值和当前行的首值之间，则无法确定位于哪一行
            if(matrix[mid][0] <= target && matrix[mid][n - 1] >= target)
            {
                row = mid;
                break;
            }
            else if(matrix[mid][0] > target)
            {
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }    
        }
        //目标值不在任一行之中，直接返回false；不要判断条件也能返回正确结果，但该条件更符合逻辑
        if(left > right)    return false;   
        left = 0, right = n - 1;
        while(left <= right)
        {
            mid = (left + right) / 2;
            if(matrix[row][mid] == target)
                return true;
            else if(matrix[row][mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return false;
    }
};
/**
矩阵和数组通过坐标对应，直接进行二分法查找
*/
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty() || matrix[0].empty())
            return false;
        int m = matrix.size(), n = matrix[0].size();
        int left = 0, right = m * n - 1, mid = 0;
        while(left <= right)
        {
            mid = (left + right) / 2;
            if(matrix[mid / n][mid % n] == target)
                return true;
            else if(matrix[mid / n][mid % n] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return false;
    }
};

Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). LeetCode

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
54
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int length = nums1.size() + nums2.size();
        vector<int> nums;
        int i = 0, j = 0, k = 0;
        double median = 0.0;
        if(nums1.empty() && nums2.empty())
            return 0.0;
        else if(nums1.empty())
            nums = nums2;
        else if(nums2.empty())
            nums = nums1;
        else
        {
            while(i < nums1.size() && j < nums2.size())
            {
                if(nums1[i] > nums2[j])
                {
                    nums.push_back(nums2[j]);
                    j++;
                }
                else
                {
                    nums.push_back(nums1[i]);
                    i++;
                }
            }
            while(i < nums1.size())
                nums.push_back(nums1[i++]);
            while(j < nums2.size())
                nums.push_back(nums2[j++]);
        }
        if(length % 2 == 1)
            median = nums[length / 2];
        else
            median = (nums[length / 2 - 1] + nums[length / 2]) / 2.0;
        return median;
    }
};
/*利用STL函数merge()合并两个已排序的向量，也可将两个向量首尾拼接，然后调用sort()函数*/
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) 
{
    int length = nums1.size() + nums2.size();
    vector<int> nums(length);
    double median = 0.0;       
    merge(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), nums.begin());
    if(length % 2 == 1)
        median = nums[length / 2];
    else
        median = (nums[length / 2 - 1] + nums[length / 2]) / 2.0;
    return median;
}