Ylin's Blog
0%

59:二分查找

发表于 更新于 分类于
本文字数： 3k 阅读时长 ≈ 3 分钟

开始算法的简单学习，今天先从二分查找法开始

二分查找

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binary_search(int start,int end,int key){
    int ret = -1;
    int mid;
    while (start <= end){
        mid = start + ((end - start) >> 1);
        if(arr[mid] < key)
            start = mid + 1;
        else if(arr[mid] > key)
            end = mid - 1;
        else{
            ret = mid;
            break;
        }
    }
    return ret;
}

这个是常用的二分法的代码实现，但是在这里我们仍然有很多要注意的地方：

while的循环条件与start end更新

有时候会疑惑循环不变量中我们什么时候使用<或<=。而在start和end的更新中不知道什么时候使用+1或-1或不变。我们需要理解什么情况下怎么去使用。

当有序数组的数据呈闭区间的时候，即[start,end]。我们令：

1
2
3
4
5
while(start <= end)		//当我们考虑start=end时，条件必须成立，所以等于关系也是其中的一种情况
...
start = mid + 1		//由于每一次的比较中，先前mid的值经过了一次比较，所以需要+1-1来避免重复比较
...
end = mid - 1

当有序数组存在开区间时，如[) (] ()，实际上它们都隐含了一个信息——start!=end，否则区间是不成立的，因此：

1
2
3
4
while(start < end)	//当start=end时，搜索区间实际上是不成立的
...
start = ？？？	//这个和左右的开闭性相关，要考虑什么时候该包括，什么时候不该包括，应该明确有效的搜索区间的范围是什么
end = ？？？

二分法解题思路

我们刚刚实现的是bsearch，即二分查找匹配的数值，实际上更多时候我们需要查找的是一个区间，即在数组内查找第一个不小于X的数值的下标：

1
2
3
4
5
6
7
8
9
10
11
12
int lower_bound(vector<int> arr, int target){
    left = 0;
    right = arr.size() - 1;
    while (left <= right){
        int mid = left + (right-left)>>1;
        if (arr[mid] < target)
            left = mid + 1;
        else:
        	right = mid -1;
    }
    return left;
}

现在，如果程序要求我们返回数组中一个=\>\>=\<\<=某个数的起始下标，实际上可以根据数组的有序性，将他们联系起来：

  • >= 这个是最基本的我们binary_search的返回值X就是它的左边界，得到答案 X
  • > 我们可以把这个问题的转换成，>= x+1 ，得到答案X+1
  • < 实际上就是>=问题的补集，得到答案(>=x) - 1
  • <= 是>问题的补集，我们可以得到答案 （>x）-1

以后遇到这种问题，都可以通过这种转换的思想来实现

练习：

704. 二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int start = 0;
        int end = nums.size()-1;

        while (start <= end){
            int mid = end + (start-end)/2;	//这里的除法我一开始使用了位运算，但是由于这里会涉及到有符号整数的运算，所以不能使用位运算
            int num = nums[mid];
            if(target > num)
                start = mid + 1;
            else if (target < num)
                end = mid - 1;
            else {
                return mid;
            }
        }
        return -1;
    }
};

34. 在排序数组中查找元素的第一个和最后一个位置

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
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = lower_bound(nums,target);
        if(nums.empty() || left == nums.size() || nums[left]!=target ){
            //当left==len(nums)时，说明数组中没有>=target的数
            return vector<int>{-1,-1};
        }
        int right = lower_bound(nums,target+1)-1;
        return vector<int>{left,right};

    }
    //返回>=target的第一个数
    int lower_bound(vector<int>& nums,int target){
         int start = 0;
         int end = nums.size() - 1;
         while (start <= end){
            int mid = (end - start)/2 + start;
            if(nums[mid] < target){
                start = mid + 1;
            }else{
                end = mid -1;
            }
         }
        return start;
    }
};

441. 排列硬币

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int arrangeCoins(int n) {
        if(n==1) return 1;
        int start = 1;
        int end = n;
        while (start <= end){
            long mid = start + ((end - start)>>1);
            if (mid*(mid+1)/2 <= n)	//更新比较条件
                start = mid +1;
            else
                end = mid-1;
        }
        return start-1;		//由于得到的是大于n的阶层数，所以想要得到能完整标识的阶层数要-1
    }
};

367. 有效的完全平方数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isPerfectSquare(int num) {
        int start = 1;
        int end = num;
        while(start <= end){
            long mid = start + ((end -start)>>1);
            if(mid*mid==num){
                return true;
            }else if(mid*mid >num){
                end = mid-1;
            }else{
                start = mid +1;
            }
        }
        return false;
    }
};