LeetCode|LeetCode 专题（二分查找） LeetCode专题：二分查找

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 -1l = 0 r = size - 1while 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 -1l = 0 r = size - 1while 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 ldef 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 题：数字在排序数组中出现的次数。
【LeetCode|LeetCode 专题（二分查找）】（本节完）