代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
二分查找是一种非常高效的查找算法,高效到什么程度呢?我们来分析一下它的时间复杂度。
假设数据大小是 n,每次查找后数据都会缩小为原来的一半,也就是会除以 2。最坏情况下,直到查找区间被缩小为空,才停止。
被查找区间的大小变化为:
n, n/2, n/4, n/8, ..., n/(2^k)
可以看出来,这是一个等比数列。其中 n/(2^k)=1
时,k 的值就是总共缩小的次数。而每一次缩小操作只涉及两个数据的大小比较,所以,经过了 k 次区间缩小操作,时间复杂度就是 O(k)。通过 n/(2^k)=1
,我们可以求得 k=log2n
,所以时间复杂度就是 O(logn)。
注意容易出错的 3 个地方。
low <= high
,而不是 low < high
;mid = (low + high) / 2
,但是如果 low 和 high 比较大的话,low + high
可能会溢出,所以这里写为 mid = (low + high) >>> 1
;low = mid + 1
、high = mid - 1
。非递归实现:
public class BinarySearch {
private static int search(int[] nums, int low, int high, int val) {
while (low <= high) {
int mid = (low + high) >>> 1;
if (nums[mid] == val) {
return mid;
} else if (nums[mid] < val) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
/**
* 二分查找(非递归)
*
* @param nums 有序数组
* @param val 要查找的值
* @return 要查找的值在数组中的索引位置
*/
private static int search(int[] nums, int val) {
return search(nums, 0, nums.length - 1, val);
}
public static void main(String[] args) {
int[] nums = {1, 2, 5, 7, 8, 9};
// 非递归查找
int r1 = search(nums, 7);
System.out.println(r1);
}
}
递归实现:
public class BinarySearch {
private static int searchRecursive(int[] nums, int low, int high, int val) {
while (low <= high) {
int mid = (low + high) >>> 1;
if (nums[mid] == val) {
return mid;
} else if (nums[mid] < val) {
return searchRecursive(nums, mid + 1, high, val);
} else {
return searchRecursive(nums, low, mid - 1, val);
}
}
return -1;
}
/**
* 二分查找(递归)
*
* @param nums 有序数组
* @param val 要查找的值
* @return 要查找的值在数组中的索引位置
*/
private static int searchRecursive(int[] nums, int val) {
return searchRecursive(nums, 0, nums.length - 1, val);
}
public static void main(String[] args) {
int[] nums = {1, 2, 5, 7, 8, 9};
// 递归查找
int r2 = searchRecursive(nums, 7);
System.out.println(r2);
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。