模板整理自大雪菜老师。链接

算法思路：假设目标值在闭区间 [l, r] 中， 每次将区间长度缩小一半，当l = r时，我们就找到了目标值。

版本1
当我们将区间 [l, r] 划分成 [l, mid] 和 [mid + 1, r] 时，其更新操作是 r = mid 或者 l = mid + 1；计算 mid 时不需要加1。

C++ 代码模板：

 1 int bsearch_1(int l, int r)
 2 {
 3     while (l < r)
 4     {
 5         int mid = l + r >> 1;
 6         if (check(mid)) r = mid;
 7         else l = mid + 1;
 8     }
 9     return l;
10 }

版本2
当我们将区间 [l, r] 划分成 [l, mid - 1] 和 [mid, r] 时，其更新操作是 r = mid - 1 或者 l = mid；此时为了防止死循环，计算 mid 时需要加1。

C++ 代码模板：

 1 int bsearch_2(int l, int r)
 2 {
 3     while (l < r)
 4     {
 5         int mid = l + r + 1 >> 1;
 6         if (check(mid)) l = mid;
 7         else r = mid - 1;
 8     }
 9     return l;
10 }

现在来讲什么时候使用模板一和模板二，如图

例题

x 的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

 

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

 代码：

 1 class Solution {
 2     public int mySqrt(int x) {
 3         long l=0, r = x;
 4 
 5         while(l<r){
 6             long mid = l + r + 1 >> 1;
 7             if((long)mid * mid <= x) {
 8                 l = mid;
 9             }else{
10                 r = mid-1;
11             }
12         }
13         return (int)r;
14     }
15 }

搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

 

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

示例 4:

输入: nums = [1,3,5,6], target = 0
输出: 0

示例 5:

输入: nums = [1], target = 0
输出: 0

 代码：

 1 class Solution {
 2     public int searchInsert(int[] nums, int target) {
 3         int n = nums.length;
 4 
 5         if(n == 0 || nums[n-1] < target){
 6             return n;
 7         }
 8 
 9         int l = 0, r = n-1;
10         while(l<r){
11             int mid = l+r >> 1;
12             if(nums[mid] >= target){
13                 r = mid;
14             }else{
15                 l = mid+1;
16             }
17         }
18         return r;
19     }
20 }

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

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：

• 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

 

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

代码

 1 class Solution {
 2     public int[] searchRange(int[] nums, int target) {
 3         int n = nums.length;
 4         if (n == 0){
 5             return new int[]{-1, -1};
 6         }
 7 
 8         int l = 0, r = n-1;
 9         while (l < r){
10             int mid = l+r >> 1;
11             if (nums[mid] >= target){
12                 r = mid;
13             }else{
14                 l = mid+1;
15             }
16         }
17         if (nums[r] != target){
18             return new int[]{-1, -1};
19         }
20         int left = l;
21 
22         l = 0;
23         r = n-1;
24         while (l<r){
25             int mid = l + r + 1 >>1;
26             if(nums[mid]<=target){
27                 l = mid;
28             }else{
29                 r = mid-1;
30             }
31         }
32         int right = r;
33         return new int[]{left, right};
34     }
35 }