二分查找(Binary Search)算法,也叫折半查找算法,当我们要从一个序列中查找一个元素的时候,二分查找是一种非常快速的查找算法,二分查找是针对有序数据集合的查找算法,二分查找是针对有序数据集合的查找算法,如果是无序数据集合就遍历查找
image.png
本质
二分查找之所以快速,是因为它在匹配不成功的时候,每次都能排除剩余元素中一半的元素。因此可能包含目标元素的有效范围就收缩得很快,而不像顺序查找那样,每次仅能排除一个元素。
一个有序的数组中查找某个数字是否存在
package com.david.alth.half;
/**
*二分法标准
*/
public class HalfDemo1 {
public static int binarySearch(int[] nums, int t) {
//低位索引
int low = 0;
//高位索引
int high = nums.length - 1;
//中间索引
int mid = 0;
while (low <= high) {
mid = (low + high) / 2;
//等于半数
if (t == nums[mid]) {
return mid;
}
//半数以里
else if(t < nums[mids]) {
high = mid - 1;
}
//半数以外
else {
low = mid + 1;
}
}
return -1;
}
public static void main(String[] args) {
//有序数组
int[] nums = {3, 12, 24, 31, 46, 48, 52, 66, 69, 79, 82};
System.out.println(binarySearch(nums, 66));
}
}
/*
* 递归实现
*/
public int bsearch(int[] a, int n, int val) {
return bsearchInternally(a, 0, n - 1, val);
}
private int bsearchInternally(int[] a, int low, int high, int value) {
if (low > high) return -1;
int mid = (low + high) / 2;
if (a[mid] == value) {
return mid;
}
else if (a[mid] < value) {
return bsearchInternally(a, mid - 1, high, value);
} else {
return bsearchInternally(a, low, mid - 1, value);
}
}
经典案例
一个有序数组有一个数出现1次,其他数出现2次,找出出现一次的数
比如:1 1 2 2 3 3 4 4 5 5 6 6 7 出现1次的数是7
暴力:
O(n)
hash:
O(n)
关键:时间复杂度 O(logn)
思路:
使用二分查找: 1 有序、 2、时间复杂度 O(logn)
偶数位索引跟后面的比相同,奇数位索引跟前面的比相同 则说明前面的都对
偶数位索引跟前面的比相同,奇数位索引跟后面的比相同 则说明后面的都对
package com.david.alth.half;
public class HalfDemo2 {
public static int binarySearch(int[] nums) {
//低位索引
int low = 0;
//高位索引
int high = nums.length - 1;
//中间索引
int mid = 0;
while (low <= high) {
mid = (low + high) / 2;
//偶数位
if(mid % 2 == 0) {
//与后面的数相等
if (nums[mid] == nums[mid + 1]) {
//前面的都对
low = mid + 1;
}
//与前面的数相等
else if (nums[mid] == nums[mid - 1]) {
//后面的都对
high = mid - 1;
}
//就是这个数
else {
return nums[mid];
}
}
//奇数位
else {
//与前面的数相等
if (nums[mid] == nums[mid - 1]) {
//前面的都对
low = mid + 1;
}
//与后面的数相等
else if (nums[mid] == nums[mid + 1]) {
//后面的都对
high = mid - 1;
} else {
return nums[mid];
}
}
}
//low=high
return nums[low];
}
public static void main(String[] args) {
int[] nums = {1, 2, 2, 3, 3, 4, 4, 5, 5};
System.out.println(binarySearch(nums));
}
}
时间复杂度
时间复杂度就是 O(logn)
优缺点
优点:速度快,不占空间,不开辟新空间
缺点:必须是有序的数组,数据量太小没有意义,但数据量也不能太大,因为数组要占用连续空间
应用
有序的查找都可以使用二分法。
如何快速定位出一个IP地址的归属地?
如果IP区间与归属地的对应关系不经常更新,我们可用先预处理这12万条数据,让其按照起始IP从小到大排序。如何来排序呢?我们知道,IP 地址可以转化为 32 位的整型数。所以,我们可以将起始地址,按照对应的整型值的大小关系,从小到大进行排序。
当我们要查询某个IP归属地时,我们可以先通过二分查找,找到最后一个起始 IP 小于等于这个IP的IP区间,然后,检查这个 IP 是否在这个 IP 区间内,如果在,我们就取出对应的归属地显示;如果不在,就返回未查找到。
网友评论