LeetCode 专题 ：二分查找
2019-05-26 本文已影响0人
李威威
LeetCode 第 704 题是二分查找的模板问题。
LeetCode 第 704 题：二分查找
传送门：704. 二分查找。
给定一个
n个元素有序的（升序）整型数组nums和一个目标值target，写一个函数搜索nums中的target，如果目标值存在返回下标，否则返回-1。示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1提示：
- 你可以假设
nums中的所有元素是不重复的。n将在[1, 10000]之间。nums的每个元素都将在[-9999, 9999]之间。
标准的二分查找实现
循环实现
Java 代码：
public class BinarySearch {
/**
* 首先要求带查找的数组应该是排好序的
*
* @param arr
* @return
*/
public static int search(int[] arr, int target) {
// 首先保证数组是有序的，否则不能使用二分查找法
SortTestHelper.testSorted(arr);
int l = 0;
int r = arr.length - 1;
// arr[0,r]
while (l <= r) {
// int mid = (l + r) / 2;
int mid = l + (r - l) / 2;
if (arr[mid] == target) {
return mid;
}
if (target < arr[mid]) {
// 回到定义中就好理解了
r = mid - 1;
} else {
l = mid + 1;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {1, 3, 5, 6, 8, 9, 13, 16, 17, 24, 56, 78};
int search = search(arr, 17);
System.out.println(search);
}
}
递归实现
可以使用递归的方式实现二分查找。递归实现通常思维起来更容易，但递归在性能上会略差，因为会调用系统栈。
Java 代码：
public class BinarySearch2 {
/**
* 首先要求带查找的数组应该是排好序的
*
* @param arr 待查找的已经排好序的数组
* @param target 待查找的数
* @param left 左边界，可以取到
* @param right 右边界，可以取到
* @return
*/
public static int binarySearch(int[] arr, int target, int left, int right) {
if (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (target < arr[mid]) {
return binarySearch(arr, target, left, mid - 1);
} else if (target > arr[mid]) {
return binarySearch(arr, target, mid + 1, right);
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {1, 3, 5, 6, 8, 9, 13, 16, 17, 24, 56, 78};
int search = binarySearch(arr, 17, 0, arr.length - 1);
System.out.println(search);
}
}
注意：1、先写递归到底的情况；
2、注意下面的这个代码片段
else if (target < arr[mid]) {
return binarySearch(arr, target, left, mid - 1);
} else if (target > arr[mid]) {
return binarySearch(arr, target, mid + 1, right);
}
一定要写 return 语句，要不然总是返回 。
“好用的”二分查找模板
这里推荐的“好用的”二分法模板是“大雪菜”整理的二分查找模板，传送门：二分查找算法模板，我个人觉得使用这个模板可以减少编码出错的可能，编码也比较简单。
Python 代码：
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
size = len(nums)
if size == 0:
return -1
l = 0
r = size - 1
while l < r:
mid = l + (r - l + 1) // 2
if nums[mid] <= target:
# mid 在，因此，不能排除 mid
l = mid
else:
assert nums[mid] > target
# mid 不在，所以可以排除 mid
r = mid - 1
# 最后要判断一下
if nums[l] == target:
return l
return -1
说明：1、mid = l + (r - l + 1) // 2 这些写法中点靠右边，而底下的逻辑是从右边向左边靠拢的，因此不会出现死循环；
2、为了避免不存在的情况出现，最后要判断一下，那个数是不是我们要找的数。
Python 代码：
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
size = len(nums)
if size == 0:
return -1
l = 0
r = size - 1
while l < r:
mid = l + (r - l) // 2
if nums[mid] < target:
# mid 可以排除，所以要 + 1
l = mid + 1
else:
assert nums[mid] >= target
# mid 不能排除，所以至少是 mid 这个位置
r = mid
# 为了避免不存在的情况出现，最后要判断一下
if nums[l] == target:
return l
return -1
练习
《剑指 Offer》（第 2 版）第 56 题：数字在排序数组中出现的次数
传送门：数字在排序数组中出现的次数。
统计一个数字在排序数组中出现的次数。例如输入排序数组[1, 2, 3, 3, 3, 3, 4, 5]和数字3，由于3在这个数组中出现了4次，因此输出4。
样例：
输入：[1, 2, 3, 3, 3, 3, 4, 5] , 3
输出：4
分析：我们只要写出一个“返回大于等于 target 的第 1 个数”的辅助方法就可以了。
Python 代码：
class Solution(object):
# 返回大于等于 target 的第 1 个数
def get_left(self, nums, target):
# [2,3,4,5,5,5,5,5,5,5]
# [1,1,1,1,1,1,1,1,1,2,3,4,5,5,5,5,5,5,5]
if nums[0] == target:
return 0
l = 1
# 思考清楚，这里为什么写 len(nums) 而不是 len(nums) - 1
r = len(nums)
while l < r:
mid = l + (r - l) // 2
if nums[mid] < target:
l = mid + 1
else:
assert nums[mid] >= target
# 不能排除 mid
r = mid
return l
def getNumberOfK(self, nums, k):
"""
:type nums: list[int]
:type k: int
:rtype: int
"""
size = len(nums)
if size == 0:
return 0
return self.get_left(nums, k + 1) - self.get_left(nums, k)
参考资料：1、你真的会写二分查找吗；
2、《剑指 Offer》（第 2 版）第 56 题：数字在排序数组中出现的次数。
（本节完）
