二分查找一般解法

二分查找模板

二分查找一般容易犯错的地方有3个:

  • 应该给mid加1还是应该减1,还是不加不减
  • 上层的while循环里面的条件应该是left < right还是 left <= right
  • 计算mid时,最好是采用mid = left + (right - left)/2而不是mid = (left + right) /2。因为这样可以避免int溢出。


二分查找的一般框架为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length ...;

while(...) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
...
} else if (nums[mid] < target) {
...
} else if (nums[mid] > target) {
...
}
}
return ...
}

上面框架中省略的地方,其实就是比较容易出问题的地方。


下面直接给出二分查找的算法模板,一般只需要熟记其中之一就好了。我一般都采样第一个:


总结一下2个模板的记忆方法:

  • 如果初始化right = nums.length -1, 那么使用left <= right,并且right = mid - 1
  • 如果初始化right = nums.length那么使用left < right, 并且right = mid

    模板1

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1; //注意

    while( left <= right ) { //注意
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) {
    //找到目标值的相关逻辑
    return mid;
    } else if (nums[mid] < target) {
    left = mid + 1; //注意
    } else if (nums[mid] > target) {
    right = mid - 1; //注意
    }
    }
    //没找到目标值的相关逻辑
    return -1;
    }

    模板2

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length; //注意

    while( left < right ) { //注意
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) {
    //找到目标值的相关逻辑
    return mid;
    } else if (nums[mid] < target) {
    left = mid + 1;
    } else if (nums[mid] > target) {
    right = mid //注意
    }
    }
    //没找到目标值的相关逻辑
    return -1;
    }


下面通过一些例子来使用一下模板

寻找一个数

这个场景是最简单的,肯能也是大家最熟悉的,即在递增序列中搜索一个数,如果存在,返回其索引,否则返回 -1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1; //注意

while(left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1; //注意
} else if (nums[mid] > target) {
right = mid - 1; //注意
}
}
return -1;
}

LeetCode上面有一个题目,[374. 猜数字大小] 其实就是最简单和标准的二分查找算法。

二分查找的变种问题

查找左右边界


这类题目一般的特点为:

  • 数组有序,但是有重复元素
  • 数组部分有序,不包含重复元素
  • 数组部分有序,包含重复元素。

查找左边界


既然要寻找左边界,搜索范围就需要从右边开始,不断往左边收缩,也就是说即使我们找到了nums[mid] == target, 这个mid的位置也不一定就是最左侧的那个边界,我们还是要向左侧查找,所以我们在nums[mid]偏大或nums[mid]就等于目标值的时候,继续收缩右边界, 不过需要注意最终while循环外需要外检查一下边界情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int left_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
// 搜索区间为 [left, right]
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
// 搜索区间变为 [mid+1, right]
left = mid + 1;
} else if (nums[mid] > target) {
// 搜索区间变为 [left, mid-1]
right = mid - 1;
} else if (nums[mid] == target) {
// 收缩右侧边界
right = mid - 1;
}
}
// 检查出界情况
if (left >= nums.length || nums[left] != target)
return -1;
return left;
}

### 查找右边界
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int right_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 这里改成收缩左侧边界即可
left = mid + 1;
}
}
// 这里改为检查 right 越界的情况,见下图
if (right < 0 || nums[right] != target)
return -1;
return right;
}
## 参考文章:

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×