二分查找

Posted on   |   In   |  

二分查找的应用

二分查找的题目

以前写的题目：

max mean

aggressive cows

cable master

leetcode:

First Bad Version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int lb = 0;
        int ub = n;
        
        while(ub - lb > 1){
            int mid = lb + (ub-lb)/2;
            if (isBadVersion(mid)){
                ub = mid;
            }else{
                lb = mid;
            }
        }
        return ub;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int lb = 1;
        int ub = n;
        
        while(ub > lb){
            int mid = lb + (ub-lb)/2;
            if (isBadVersion(mid)){
                ub = mid;
            }else{
                lb = mid + 1 ;
            }
        }
        return ub;
    }
};

Search Insert Position

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int lb = -1;
        int ub = nums.size();
    
        while(ub - lb > 1){
            int mid = (lb + ub)/2;   //此题不用考虑数组越界(lb+ub)
            if (nums[mid] < target)
                lb = mid;
            else
                ub = mid;
        }
        return ub;
    }
};
1
2
3
4
5
6
7
8
9
//直接使用lower_bound
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
       
       return (lower_bound(nums.begin(), nums.end(), target)-nums.begin());
        
    }
};

Search in Rotated Sorted Array I

注意此题与上一题的区别:此题是在数组中找到目标元素的下标，而上面一题是找到最佳插入的位置。
思路:对于经过旋转过的升序数组，首先需要明确的是，给定一个任意元素(下标为l),数组的下标范围是[lb, ub] (lb<=l<=ub),那么一定存在要么(lb, l)为升序排列,要么(l, ub)为升序排列，下面的code就是基于此思路的
详细的解题思路及图

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
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int lb = 0;
        int ub = nums.size() -1;
        
        while(ub >= lb){
            int mid = (lb + ub)/2;
            if (nums[mid] == target) return mid;
            
            if (nums[mid] >= nums[lb]){  //从lb到mid为升序

                if (nums[lb] <= target &&  target < nums[mid])
                    ub = mid-1;
                else
                    lb = mid + 1;
                
            }else{                   //从mid到ub为升序
                if(nums[mid] < target && target <= nums[ub])
                    lb = mid + 1;
                else
                    ub = mid -1 ;
            }
        }
        
        return -1;
    }
};

81. Search in Rotated Sorted Array II

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
class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int lb = 0;
        int ub = nums.size() -1;
        
        while(ub >= lb){
            int mid = lb +(ub - lb)/2;
            
            if (nums[mid] == target){
                    return true;
            }
            
            if (nums[mid] > nums[lb]){   //(lb,mid)有序
                if( nums[lb] <= target && target < nums[mid])
                    ub = mid - 1;
                else
                    lb = mid + 1;
            }else if (nums[mid] < nums[lb]){                        //(mid, ub)有序
                if(nums[mid] < target && target <= nums[ub])
                    lb = mid + 1;
                else
                    ub = mid - 1;
            }else{               //nums[mid] == nums[lb]出现的情况:(1)1 3 1 1 1(2)1 3，这个时候需要将lb++;
                lb++;
            }
        }
        
        return false;
    }
};