概念
二分查找(Binary Search)算法,也叫折半查找算法
当我们要从一个序列中查找一个元素的时候,二分查找是一种非常快速的查找算法
二分查找是针对有序数据集合的查找算法,如果是无序数据集合就遍历查找


本质
二分查找之所以快速,是因为它在匹配不成功的时候,每次都能排除剩余元素中一半的元素。因此可能包含目标元素的有效范围就收缩得很快,而不像顺序查找那样,每次仅能排除一个元素。
小例子
一个有序的数组中查找某个数字是否存在:
package com.rubin.algorithm.search;
public class BinarySearch {
/**
* 经典二分查找
*
* @param nums
* @param item
* @return
*/
public static int normalBinarySearch(int[] nums, int item) {
int low = 0, high = nums.length - 1, mid;
while (low <= high) {
mid = (low + high) / 2;
int midValue = nums[mid];
if (midValue == item) {
return mid;
} else if (midValue > item) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
/**
* 递归二分查找
*
* @param nums
* @param item
* @return
*/
public static int recursionBinarySearch(int[] nums, int item) {
return doRecursionBinarySearch(nums, item, 0, nums.length - 1);
}
private static int doRecursionBinarySearch(int[] nums, int item, int low, int high) {
if (low > high) {
return -1;
}
int mid = (low + high) / 2;
int midValue = nums[mid];
if (midValue == item) {
return mid;
} else if (midValue > item) {
return doRecursionBinarySearch(nums, item, low, mid - 1);
} else {
return doRecursionBinarySearch(nums, item, mid + 1, high);
}
}
/**
* 一个有序数组有一个数出现1次,其他数出现2次,找出出现一次的数
*
* @param nums
* @return
*/
public static int onceBinarySearch(int[] nums) {
int low = 0, high = nums.length - 1, mid;
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]) {
high = mid - 1;
}
// 奇数位跟前面的相等 说明前的都对
else if (nums[mid] == nums[mid - 1]) {
low = mid + 1;
}
// 前后都不相等 就是该数
else {
return nums[mid];
}
}
}
// low == high
return nums[low];
}
public static void main(String[] args) {
int[] nums = {2, 4, 5, 7, 10, 24, 36, 89};
System.out.println(normalBinarySearch(nums, 5));
System.out.println(recursionBinarySearch(nums, 2));
int[] onceNums = {1, 1, 2, 2, 3, 4, 4, 5, 5};
System.out.println(onceBinarySearch(onceNums));
}
}
时间复杂度
时间复杂度就是 O(logn)
优缺点
优点:速度快,不占空间,不开辟新空间
缺点:必须是有序的数组,数据量太小没有意义,但数据量也不能太大,因为数组要占用连续的空间
应用
有序的查找都可以使用二分法。
以上就是本文的全部内容。欢迎小伙伴们积极留言交流~~~
文章评论