01月07, 2019

二分查找BinarySearch实现

二分查找,也叫折半查找,是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则意味着找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

在这里我们以java语言来实现,有递归与非递归。

import java.util.Arrays;

import edu.princeton.cs.algs4.In; //导入算法4的特有库
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class BinarySearch {

    //递归
//    public static int rank(int key, int[] a) {
//        return rank(key, a, 0, a.length - 1);
//    }
//    java的函数重载
//    public static int rank(int key, int[] a, int lo, int hi) {
//        if(lo > hi) return -1;
//        int mid = lo + (hi - lo) / 2;
//        if      (key < a[mid]) return rank(key, a, lo, mid - 1);
//        else if (key > a[mid]) return rank(key, a, mid + 1, hi);
//        else                                          return mid;
//    }

    public static int rank(int key, int[] a) {
        int lo = 0;
        int hi = a.length - 1;
        while ( lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if      (key < a[mid]) hi = mid - 1;
            else if (key > a[mid]) lo = mid + 1;
            else                     return mid;
        }
        return -1;
    }
    public static void main(String[] args) {
        In in = new In(args[0]);
        int[] whitelist = in.readAllInts();
                /*读取数组中的值*/        

        Arrays.sort(whitelist);
                /*对数组进行排序*/        

        while (!StdIn.isEmpty()) {
            int key = StdIn.readInt(); /*输入需查找的值*/
            if (rank(key, whitelist) == -1)
                StdOut.println(key);  /*如果在whitelist数组中找不到key,则返回当前的key值*/
        }
    }
}

例如: whitelist为 1 3 4 8 2 5 0 3 key为2

先将whitelist从小到大排序为 0 1 2 3 3 4 5 8

然后中间值为3,2<3,故在左半部分查找,左半部分中间值为1,2>1,故在左半部分的右半部分查找,最后找到。

本文链接:https://lyuly.com/post/binarysearch.html

-- EOF --

Comments

评论加载中...

注:如果长时间无法加载,请针对 disq.us | disquscdn.com | disqus.com 启用代理。