怎么破解软件付费内容
转载声明：
本文为摘录自“csdn博客”，版权归原作者所有。
温馨提示：
为了更好的体验，请点击原文链接进行浏览
摘录时间：
2020-10-13 15:14:06
二分查找法只能应用于有序的数组。
将要查找的元素和数组中间的元素作比较，
如果要查找的元素比数组中间的元素小，那么到左半部分查找；
如果要查找的元素比数组中间的元素大，那么到右s半部分查找。
以此类推，直到找到为止。
如果没有找到，则返回 -1。
最坏时间复杂度：O(logn)
最优时间复杂度：O(1)
平均时间复杂度：O(logn)
最坏空间复杂度：迭代 O(1)，递归 O(logn)
非递归实现
public class BinarySearch {
private BinarySearch() {
}
public static int find(int[] arr, int target) {
if (arr == null || arr.length == 0) {
return -1;
}
int l = 0;
int r = arr.length - 1;
int mid;
while (l <= r) {
mid = l + ((r - l) >> 1);
if (arr[mid] == target) {
return mid;
} else if (arr[mid] > target) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return -1;
}
/**
* 测试非递归的二分查找算法
*/
public static void main(String[] args) {
int N = 1000000;
int[] arr = new int[N];
for(int i = 0 ; i < N ; i ++) {
arr[i] = i;
}
// 对于我们的待查找数组[0...N)
// 对[0...N)区间的数值使用二分查找，最终结果应该就是数字本身
// 对[N...2*N)区间的数值使用二分查找，因为这些数字不在arr中，结果为-1
for(int i = 0 ; i < 2 * N ; i ++) {
int v = BinarySearch.find(arr, i);
if (i < N) {
assert v == i;
} else {
assert v == -1;
}
}
return;
}
}
递归实现
public class BinarySearch2 {
private BinarySearch2() {
}
public static int find(int[] arr, int target) {
if (arr == null || arr.length == 0) {
return -1;
}
return find(arr, 0, arr.length - 1, target);
}
private static int find(int[] arr, int l, int r, int target) {
if (l > r) {
return -1;
}
int mid = l + ((r - l) >> 1);
if (arr[mid] == target) {
return mid;
} else if (arr[mid] > target) {
return find(arr, l, mid - 1, target);
} else {
return find(arr, mid + 1, r, target);
}
}
/**
* 测试递归的二分查找算法
*/
public static void main(String[] args) {
int N = 1000000;
int[] arr = new int[N];
for(int i = 0 ; i < N ; i ++) {
arr[i] = i;
}
// 对于我们的待查找数组[0...N)
// 对[0...N)区间的数值使用二分查找，最终结果应该就是数字本身
// 对[N...2*N)区间的数值使用二分查找，因为这些数字不在arr中，结果为-1
for(int i = 0 ; i < 2 * N ; i ++) {
int v = BinarySearch2.find(arr, i);
if (i < N) {
assert v == i;
} else {
assert v == -1;
}
}
return;
}
}
