关于面试:java-如何实现-binary-search-二分查找法

程序查找

如果让你在一堆书架上找到本人想要的书，你会怎么找呢？

实际上最简略最粗犷的形式就是一本一本的看过来。

这个用计算机实现就对应着程序查找。

概念

程序查找适宜于存储构造为顺序存储或链接存储的线性表。

根本思维：程序查找也称为线形查找，属于无序查找算法。从数据结构线形表的一端开始，程序扫描，顺次将扫描到的结点关键字与给定值k相比拟，若相等则示意查找胜利；若扫描完结仍没有找到关键字等于k的结点，示意查找失败。

复杂度剖析：

　
查找胜利时的均匀查找长度为：（假如每个数据元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;

当查找不胜利时，须要n+1次比拟，工夫复杂度为O(n);

所以，程序查找的工夫复杂度为O(n)。

java 代码实现

以 java 代码为例：

/*** 程序查问算法** @param arr 数组信息** @param target 目标值** @param arrLength 数组长度*/int foreachSearch(int arr[], int target, int arrLength) {    int i;    for(i = 0; i < arrLength; i++) {        if(target == arr[i]) {            return i;        }    }    return -1;}

java 改良版本

咱们这个实现版本次要是为了补救大部分网上实现的有余，很多实现就是一个 int 类型，适用范围不够宽泛。

接口定义

为了后续的拓展性，咱们定义查问接口及形象实现。

package com.github.houbb.search.api;import java.util.List;/** * @author 老马啸东风 * @since 0.0.1 */public interface ISearch<T> {    /**     * 执行元素的查问     * @param list 列表     * @param key 指标对象     * @return 后果对应的下标     * @since 0.0.1     */    int search(List<? extends Comparable<? super T>> list, T key);}

形象实现:

package com.github.houbb.search.core;import com.github.houbb.heaven.util.common.ArgUtil;import com.github.houbb.heaven.util.util.CollectionUtil;import com.github.houbb.search.api.ISearch;import com.github.houbb.search.constant.SearchConst;import java.util.List;/** * 形象查问类 * @author 老马啸东风 * @since 0.0.1 */public abstract class AbstractSearch<T> implements ISearch<T> {    @Override    public int search(List<? extends Comparable<? super T>> list, T key) {        ArgUtil.notNull(key, "key");        if(CollectionUtil.isEmpty(list)) {            return SearchConst.NOT_FOUND;        }        return this.doSearch(list, key);    }    /**     * 执行查问     * @param list 列表     * @param key key     * @return 后果     * @since 0.0.1     */    protected abstract int doSearch(List<? extends Comparable<? super T>> list, T key);}

遍历实现

实现和后面根底版本相似。

package com.github.houbb.search.core;import com.github.houbb.search.constant.SearchConst;import java.util.List;/** * 遍历查问法 * @author 老马啸东风 * @since 0.0.1 */public class ForeachSearch<T> extends AbstractSearch<T> {    @Override    @SuppressWarnings("all")    protected int doSearch(List<? extends Comparable<? super T>> list, T key) {        for(int i = 0; i < list.size(); i++) {            Comparable comparable = list.get(i);            if(comparable.compareTo(key) == 0) {                return i;            }        }        return SearchConst.NOT_FOUND;    }}

这个实现的适用范围成心被咱们放大为可比拟类型了，实际上能够更加宽泛一些，实践上只有能通过 equals() 比拟的对象都能够。

其实次要是为了兼容咱们上面要讲的二分查找法，也是咱们本文的重点。

二分查找法

遍历查问十分的简略粗犷，不过性能也是比拟差的。

如果要查找的数据曾经排序过了，比方咱们通过查看联系人时，个别能够通过姓名疾速找到大略的地位，而不是从头到尾的看一遍。

这个通过计算机实现就是二分查找法。

概念

二分搜寻（英语：binary search），也称折半搜寻（英语：half-interval search）、对数搜寻（英语：logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。

搜寻过程从数组的两头元素开始，如果两头元素正好是要查找的元素，则搜寻过程完结；

如果某一特定元素大于或者小于两头元素，则在数组大于或小于两头元素的那一半中查找，而且跟开始一样从两头元素开始比拟。

如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比拟都使搜寻范畴放大一半。

复杂度概览

步骤

（1）首先确定整个查找区间的两头地位 mid = （ left + right ）/ 2

（2）用待查关键字值与两头地位的关键字值进行比拟；

若相等，则查找胜利

若大于，则在后（右）半个区域持续进行折半查找

若小于，则在前（左）半个区域持续进行折半查找

（3）对确定的放大区域再按折半公式，反复上述步骤。

最初，失去后果：要么查找胜利， 要么查找失败。

折半查找的存储构造采纳一维数组寄存。

留神：这里有一个前提，数组必须是有序的。如果元素无序怎么办呢？当然是先执行排序，而后再通过折半查找了。

排序算法不是本文重点，能够参考：

7 天工夫，我整顿并实现了这 9 种最经典的排序算法

java 代码实现

咱们先来看一下网上最常见的两种实现。

递归实现

public static int binarySearch(int[] arr, int start, int end, int hkey){    if (start > end)        return -1;    int mid = start + (end - start)/2;    //避免溢位    if (arr[mid] > hkey)        return binarySearch(arr, start, mid - 1, hkey);    if (arr[mid] < hkey)        return binarySearch(arr, mid + 1, end, hkey);    return mid;  }

递归实现的版本十分的简洁优雅。

循环实现

public static int binarySearch(int[] arr, int start, int end, int hkey){    int result = -1;    while (start <= end){        int mid = start + (end - start)/2;    //避免溢位        if (arr[mid] > hkey)            end = mid - 1;        else if (arr[mid] < hkey)            start = mid + 1;        else {            result = mid ;              break;        }    }    return result;}

循环实现绝对麻烦一些，不过性能个别会比递归好一点。

java 改进版本

下面的办法十分简洁，问题也同样显著。

如果我想比拟查找 String、Long 等其余常见类型怎么办呢？

咱们能够略微改进一下下面的实现：

package com.github.houbb.search.core;import com.github.houbb.search.constant.SearchConst;import java.util.List;/** * 折半 * @author 老马啸东风 * @since 0.0.1 */public class BinarySearch<T> extends AbstractSearch<T> {    @Override    @SuppressWarnings("all")    protected int doSearch(List<? extends Comparable<? super T>> list, T key) {        int low = 0;        int high = list.size()-1;        while (low <= high) {            int mid = (low+high) / 2;            Comparable comparable = list.get(mid);            if(comparable.compareTo(key) == 0) {                return mid;            } else if(comparable.compareTo(key) < 0) {                // 小于指定元素                low = mid;            } else {                // 大于指定元素                high = mid;            }        }        return SearchConst.NOT_FOUND;    }}

这里咱们将比拟对象扩大为 Comparable 对象，而后通过 compareTo 办法进行比拟。

开源工具

当然个别的查找算法到这里就完结了，然而老马却不这么认为。

知其然，知其所以然，所以咱们要学习算法原理。

小人性非异也， 善假于物也，所以咱们要学会应用工具。

算法应该被封装为简略可用的工具，便于应用。于是老马把下面的两种查问算法开源到了 maven 地方仓库，便于前期应用可拓展。

maven 引入

<dependency>    <groupId>com.github.houbb</groupId>    <artifactId>search</artifactId>    <version>0.0.1</version></dependency>

应用

遍历查问

final List<String> list = Arrays.asList("1", "2", "3", "4", "5");Assert.assertEquals(3, SearchHelper.foreach(list, "4"));

折半查问

final List<String> list = Arrays.asList("1", "2", "3", "4", "5");Assert.assertEquals(3, SearchHelper.binary(list, "4"));

小结

心愿本文对你有帮忙，如果有其余想法的话，也能够评论区和大家分享哦。

各位极客的点赞珍藏转发，是老马继续写作的最大能源！

下一节咱们将解说一下二叉查问树，感兴趣的小伙伴能够关注一波，精彩内容，不容错过。