精华内容
下载资源
问答
  • 编写程序数据序列采用二分查找和顺序查找法查找元素的下标,要求使用类模板实现(其中二分法查找算法要求用递归实现,给定数据序列有序)。
  • 数据结构与算法--查找之顺序查找和分查找 符号表的目的是将一个键和一个值关联起来,可以将一对键值插入到符号表中,也可以根据给定的键从符号表所有的键值中快速或者直接找到相对应的值。对于键和值,我们作...

    数据结构与算法--查找之顺序查找和二分查找

    符号表的目的是将一个键和一个值关联起来,可以将一对键值对插入到符号表中,也可以根据给定的键从符号表所有的键值对中快速或者直接找到相对应的值。对于键和值,我们作如下约定,以后的实现都遵循这些约定。

    • 每个键只对应一个值,也就是说不允许存在重复的键
    • 新插入的键值对在表中键已经存在,此时称为冲突,让新的值取代旧的值
    • 键不能为空null,因为在比较中会调用键的equals或者compareTo方法;若为空会造成空指针异常
    • 值不能为空null,因为在我们的实现中,当查找一个不存在的键时,默认返回null。因此我们可以用get(Key key)判断某个键在表中是否存在;也可以用put(Key key, null)将某键值对删除(延时实现)。

    无序链表的顺序查找

    顺序查找也就是遍历表中元素,链表实现即每个结点都表示一个键值对。如get(Key key)方法,查找表中所有键值对,如果匹配成功就返回相应的值,否则返回null;put(Key key, Value value)方法也是查找表中所有键值对,如果键已经存在就更新值,否则在链表头插入这个新的键值对。实现起来很简单,我们来看代码。

    package Chap8;
    
    import java.util.ArrayList;
    import java.util.Collection;
    import java.util.LinkedHashSet;
    import java.util.Set;
    
    public class SequentialST<Key, Value> {
        private Node first;
        private int N;
    
        private class Node {
            Key key;
            Value value;
            Node next;
    
            public Node(Key key, Value value, Node next) {
                this.key = key;
                this.value = value;
                this.next = next;
            }
        }
    
        public Value get(Key key) {
            for (Node cur = first; cur != null; cur = cur.next) {
                if (key.equals(cur.key)) {
                    return cur.value;
                }
            }
            return null;
        }
        // 若是键不存在,则返回一个指定的默认值
        public Value getDefault(Key key, Value value) {
            for (Node cur = first; cur != null; cur = cur.next) {
                if (key.equals(cur.key)) {
                    return cur.value;
                }
            }
            return value;
        }
    
        public void put(Key key, Value value) {
            // 如果传入null,就是删除键值对
            if (value == null) {
                delete(key);
                return;
            }
    
            for (Node cur = first; cur != null; cur = cur.next) {
                if (key.equals(cur.key)) {
                    cur.value = value;
                    return;
                }
            }
            /*  新键值对。new Node的next指向first,然后取代它成为新的first, 是以下代码的简化版
    
                Node oldfirst = first;
                first = new Node();
                first.next = oldfirst;
            */
            first = new Node(key, value, first);
            N++;
        }
    // 未采用的延时删除,使用下面的delete
    //    public void delete(Key key) {
    //        put(key, null);
    //    }
    
        public Value delete(Key key) {
            if (isEmpty()) {
                return null;
            }
    
            Node cur = first;
            Value value = null;
            // 删除的键值对如果在链表头,处理方式不一样
            if (key.equals(cur.key)) {
                value = cur.value;
                Node next = cur.next;
                // 下面三行是帮助垃圾回收
                cur.key = null;
                cur.value = null;
                cur.next = null;
                first = next;
                N--;
            } else {
                // 现在pre是first,而cur是first的下一个结点
                Node pre = cur;
                cur = cur.next;
    
                while (cur != null) {
                    if (key.equals(cur.key)) {
                        value = cur.value;
                        Node next = cur.next;
                        // 下面三行是帮助垃圾回收
                        cur.key = null;
                        cur.value = null;
                        cur.next = null;
                        pre.next = next;
                        N--;
                        return value;
                    }
                    // 下轮比较指向下一个结点,所以更新pre和cur
                    pre = cur;
                    cur = cur.next;
                }
            }
            return value;
        }
    
        public Set<Key> keys() {
            // 保证和values是一样的顺序
            Set<Key> keys = new LinkedHashSet<>();
            for (Node cur = first;cur != null;cur = cur.next) {
                keys.add(cur.key);
            }
            return keys;
        }
    
        public Collection<Value> values() {
            Collection<Value> values = new ArrayList<>();
            for (Node cur = first;cur != null;cur = cur.next) {
                values.add(cur.value);
            }
            return values;
        }
    
        @Override
        public String toString() {
            if (isEmpty()) {
                return "{}";
            }
    
            StringBuilder sb = new StringBuilder();
            sb.append("{");
            Node cur = first;
    
            while (true) {
                sb.append(cur.key).append("=").append(get(cur.key));
                if (cur.next == null) {
                    return sb.append("}").toString();
                } else {
                    sb.append(", ");
                }
                cur = cur.next;
            }
        }
        public boolean contains(Key key) {
            return get(key) != null;
        }
    
        public int size() {
            return N;
        }
    
        public boolean isEmpty() {
            return N == 0;
        }
    
        public static void main(String[] args) {
            SequentialST<String, Integer> st = new SequentialST<>();
            st.put("admin", 8888);
            st.put("password", 123456);
            st.put("pcNumber", 5);
            st.put("money", 6666);
            Integer password = st.delete("password");
            st.delete("money");
            System.out.println(password);
    
            System.out.println(st.get("pcNumber"));
            System.out.println(st.get("admin"));
            System.out.println(st.keys());
            System.out.println(st.values());
            System.out.println(st);
        }
    }

    get方法没什么好说的,有一个getDefault方法,当给出的键不存在时,将返回一个由调用者自定义的默认值。put方法中,如果值传入null,相当于是删除该键值对,所以调用了delete。否则遍历链表,如果查找到键已经存在,则用新的value取代旧的value;如果没找到,说明这是新的键值对,直接插入到链表头(相当于push操作)。

    重点看delete方法,我们并不打算用延时实现——虽然它相当简单。如下

    public void delete(Key key) {
        put(key, null);
    }

    注意:如果使用上述实现,put方法头几行判断就得去掉,否则两个方法会互相调用导致StackOverflow。我们的实现是即时删除的,其实就是链表删除结点的操作。即时delete中,需要一个Node pre指针,用于指向当前结点的前一个结点,如果你对链表结点的删除操作熟悉的话,应该清楚为什么需要这个pre指针。链表头的删除和其他地方结点的删除操作还有些不一样:删除链表头只需first.next成为新的first;其他位置的删除,删除的是结点cur,需要将cur的前一个结点pre的next指向cur的next,即pre.next = cur.next

    keysvalues方法可以返回符号表中所有的键值对,键是唯一的所以用了Set存放。

    在含有N对键值对的无序链表中,未命中和插入新键值对的比较次数均为N,命中的最坏情况为比较N次(最后一个结点才匹配成功)。

    有序数组中的二分查找

    上面链表实现的符号表中,表是无序的。如果能在插入过程中保证表一直有序,在查找的时候就不必顺序查找,使用二分查找可大大提高查找的效率。我们需要两个数组,Key[]Value[]分别存储键和值。为了保证插入过程中表一直有序,对标准的二分查找稍作修改,如下

    public int rank(Key key) {
        int low = 0;
        int high = N - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int cmp = key.compareTo(keys[mid]);
            if (cmp < 0) {
                high = mid - 1;
            } else if (cmp > 0) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        return low;
    }

    倒数第二行,未命中时原来返回-1,现在返回low——恰好是小于参数Key的键的数量,说得直白些就是在key之前的键的数量。

    插一句,二分查找的思想:首先查找的数组必须是有序的。先将被查找的键与数组中的中间键比较(如果表长度为偶数则会向下取整),若小于中间的键就在中间键的左边子数组继续查找;若大于中间的键就在中间键的右边子数组中继续查找;否则就是查找成功了。如此迭代,直到high > low终止。

    查找成功时返回的是mid,说明该键在数组中的位置就是keys[mid],小于该key的键的数量就是mid,这个很好理解。但为什么查找失败最后high > low迭代终止时,返回low就是小于key的键的数量呢?

    因为查找失败前,最后查找范围一定是只有一个元素了,此时low = high = mid, 最后一次比较后发现也不相等,它要么比mid大,要么比mid小。如果它比mid小说明它应该在mid的前一个位置,比它小的键的数量和比mid小的数量是一样的,再看代码中:if分支low没有改变,返回的low和mid值一样;如果它比mid大说明它应该在mid的后一个位置,比它小的键的数量应该比小于mid的键的数量多1(比mid大,所以把mid也算进去),再看代码中:else分支low变成了mid + 1,最后返回的low实际也是mid + 1。由此验证了,这样实现的二分查找可以返回数组中小于给定key的键的数量!

    st_rank.png

    看图加深理解:先看查找成功时,对P查找。最后一步查找,mid=6,此时命中并退出。表示P在keys[]中的位置是6,同时也表示小于P的键的数量为6;再看查找Q时的查找失败。最后一步查找时,和查找P一样low = high = mid = 6,只不过这次并不是返回mid,查找的Q大于mid位置的P,会执行else if分支,Q的位置应该在图中第二个红色箭头处,返回的low实际上等于mid + 1 = 7,结合图中,Q的位置之前确实有7个键。

    上述rank方法是全部实现的核心,现在给出全部代码,再解释其中一些方法。

    package Chap8;
    
    import java.util.*;
    
    public class BinarySearchST<Key extends Comparable<Key>, Value> {
        private Key[] keys = (Key[]) new Comparable[1];
        private Value[] values = (Value[]) new Object[1];
        private int N;
    
        public int rank(Key key) {
            int low = 0;
            int high = N - 1;
            while (low <= high) {
                int mid = low + (high - low) / 2;
                int cmp = key.compareTo(keys[mid]);
                if (cmp < 0) {
                    high = mid - 1;
                } else if (cmp > 0) {
                    low = mid + 1;
                } else {
                    return mid;
                }
            }
            return low;
        }
    
        public void put(Key key, Value value) {
            // 如果传入null,就是删除键值对
            if (value == null) {
                delete(key);
                return;
            }
    
            // 如果容量满了,增容
            if (N == keys.length) {
                resize(2 * keys.length);
            }
    
            int i = rank(key);
            // 键已经存在,新值取代旧值
            if (i < N && keys[i].compareTo(key) == 0) {
                values[i] = value;
                return;
            }
            // 否则插入新的键值对,i及之后的元素都需要后移一个位置,腾出位置i给新的键值对使用
            for (int j = N; j > i; j--) {
                keys[j] = keys[j - 1];
                values[j] = values[j - 1];
            }
            keys[i] = key;
            values[i] = value;
            N++;
        }
    
        public Value get(Key key) {
            if (isEmpty()) {
                return null;
            }
            int i = rank(key);
            if (i < N && keys[i].compareTo(key) == 0) {
                return values[i];
            } else {
                return null;
            }
        }
    
        public Value getDefault(Key key, Value defaultValue) {
            if (get(key) == null) {
                return defaultValue;
            } else {
                return get(key);
            }
        }
    
        private void resize(int max) {
            Key[] tempKeys = (Key[]) new Comparable[max];
            Value[] tempValues = (Value[]) new Object[max];
            for (int i = 0; i < N; i++) {
                tempKeys[i] = keys[i];
                tempValues[i] = values[i];
            }
            keys = tempKeys;
            values = tempValues;
        }
    
    
        public boolean isEmpty() {
            return N == 0;
        }
    
        public int size() {
            return N;
        }
    
        public int size(Key low, Key high) {
            if (high.compareTo(low) < 0) {
                return 0;
            } else if (contains(high)) {
                return rank(high) - rank(low) + 1;
            } else {
                return rank(high) - rank(low);
            }
        }
    
        public boolean contains(Key key) {
            return get(key) != null;
        }
    
        public Key min() {
            return keys[0];
        }
    
        public Key max() {
            return keys[N - 1];
        }
    
        public Value deleteMin() {
            return delete(min());
    
        }
    
        public Value delete(Key key) {
            int i = rank(key);
            Value value = null;
    
            if (keys[i].compareTo(key) == 0) {
                value = values[i];
                for (int j = i; j < N - 1; j++) {
                    keys[j] = keys[j + 1];
                    values[j] = values[j + 1];
                }
                // 防止对象游离
                keys[N - 1] = null;
                values[N - 1] = null;
                N--;
                // 如果只用了总容量的四分之一,缩减容量一半
                if (N > 0 && N == keys.length / 4) {
                    resize(keys.length / 2);
                }
            }
    
            return value;
        }
    
        public Value deleteMax() {
            return delete(max());
        }
    
        // k = rank(select(k))
        // key = select(rank(key)
        public Key select(int k) {
            return keys[k];
        }
    
        public Set<Key> keys() {
            return keys(min(), max());
        }
    
        public Collection<Value> values() {
            return values(min(), max());
        }
    
        public Collection<Value> values(Key low, Key high) {
            Collection<Value> q = new ArrayList<>();
            for (int j = rank(low); j < rank(high); j++) {
                q.add(values[j]);
            }
            if (contains(high)) {
                q.add(values[rank(high)]);
            }
            return q;
        }
    
        public Set<Key> keys(Key low, Key high) {
            // 保持原来的顺序,使用LinkedHashSet
            Set<Key> q = new LinkedHashSet<>();
            for (int j = rank(low); j < rank(high); j++) {
                q.add(keys[j]);
            }
            if (contains(high)) {
                q.add(keys[rank(high)]);
            }
            return q;
        }
    
        // 大于等于key的最小键,如果key在表中就是等于key;否则是大于key的最小键,即i的下一个位置的键
        public Key ceiling(Key key) {
            int i = rank(key);
            // i可能等于N,此时返回null,也符合
            return keys[i];
        }
    
        // 小于等于key的最大键
        public Key floor(Key key) {
            int i = rank(key);
            if (contains(key)) {
                return keys[i];
                // 考虑负数脚标的情况,i == 0会造成keys[-1]
            } else if (!contains(key) && i != 0) {
                return keys[i - 1];
            } else {
                // 表中不没有键key且i == 0,说明key是表中最小的,不存在比它还小的所以返回null
                return null;
            }
        }
    
        @Override
        public String toString() {
            if (isEmpty()) {
                return "{}";
            }
            StringBuilder sb = new StringBuilder();
            sb.append("{");
            int i = 0;
            while (true) {
                sb.append(keys[i]).append("=").append(values[i]);
                if (i == N - 1) {
                    return sb.append("}").toString();
                } else {
                    sb.append(", ");
                }
                i++;
            }
        }
    
        public static void main(String[] args) {
            BinarySearchST<Integer, Double> st = new BinarySearchST<>();
            st.put(1, 5567.5);
            st.put(5, 10000.0);
            st.put(3, 4535.5);
            st.put(7, 7000.0);
            st.put(12, 2500.0);
            st.put(10, 4500.0);
            st.put(17, 15000.5);
            st.put(15, 12000.5);
            st.deleteMax(); // 17
            st.deleteMin(); // 1
            st.delete(12); // 剩下[3, 5, 7, 10, 15]
    
            System.out.println("符号表的长度为" + st.size());
            System.out.println("[3, 6]之间有" + st.size(3, 6) + "个键");
            System.out.println("比9小的键的数量为" + st.rank(9));
            System.out.println("排在第4位置的键为" + st.select(4));
            System.out.println("大于等于8的最小键为" + st.ceiling(8));
            System.out.println("小于等于8的最大键为" + st.floor(8));
    
            System.out.println("符号表所有的键和对应的值为:" + st.keys() + " -> " + st.values());
            System.out.println("键2和键8之间的所有键及对应的值:" + st.keys(2, 8) + " -> " + st.values(2, 8));
    
            System.out.println(st);
    
        }
    
    }
    

    首先这个符号表是容量自适应的,实现见resize方法。这意味着我们不用担心数组脚标越界。思路是:当键值对个数等于数组长度时候,将数组长度扩充到原来的两倍;当键值对个数过少,等于数组长度的四分之一时,将数组长度减小到原来的一半。

    然后是很重要的方法get / put,put之前需要判断是否传入了null值,以及是否需要增容,之后使用int i = rank(key)方法定位key的位置,如果key在符号表中存在,会用新的值取代旧的值;否则在位置i处插入新的键值对,为此需要将i及其之后的元素都往后移动一个位置。get方法就很简单了,首先要判断是不是空表,因为下面调用了keys[i].compareTo(key),如果是空表,则keys[i]是null,调用compareTo会出现异常。int i = rank(key)返回的i最小就是0了,所以if里只需判断i < N以防止keys[i]越界。

    delete方法其实就是删除数组中某个元素,用int i = rank(key)快速定位到key的位置(如果key不在符号表中,删除失败返回null),i之后的元素都往前移动一个位置,最后原数组的最后一个键值对keys[N -1]values[N -1]需要置空(因为它们现在都往前移动一个位置了,这个位置已经没有作用了),随之N减少1表示删除一个键值对成功。

    min / max返回最小的键和最大的键,由于键数组本身有序,keys[0]keys[N - 1]就分别对应着最小 / 最大键。

    deleteMin / deleteMax,就是删除最小 / 最大的键并返回对应的值。

    select(int k)返回位置排在k的键。注意,细心观察可以发现select和rank之间满足如下关系。

    k = rank(select(k))
    key = select(rank(key)

    floor(Key key)返回小于等于key的最大键。还是先用int i = rank(key)定位key的位置,如果key在符号表中,直接返回keys[i];否则,我们返回的应该是keys[i - 1],这个在纸上画画就能理解了。有点要注意,如果rank(key)返回的是0,那么使用keys[i - 1]就会异常,所以对i == 0单独判断下,此时应该返回null,因为表中任意键都没有给出的key要小。

    ceiling(Key key)返回大于等于key的最小键,同样如果key在符号表中,直接返回keys[i];如果不在符号表中,还是应该返回keys[i](纸上画画吧)。

    最后我们来看看比较有意思的size(Key low, Key high) / keys(Key low, Key high) ,还有个values(Key low, Key high)原理和keys一样,这里就说前述两个。这些方法都有判断Key high在不在符号表中,这有影响吗?我们结合几个图来看看。

    无非是下面4种情况。

    st_IMG_20171013_125648.jpg

    st_IMG_20171013_125749.jpg

    可见当Key high存在于符号表中时,计算size需要进行+1操作,将high这个键也算进去;计算keys的时候也要将Key high算进去。

    由于是数组实现的,插入和删除都是相当麻烦的,不过查找效率很高。上面链表实现的顺序查找,在插入和删除上有优势,但是查找效率挺低的。有没有办法整合这两者的优点呢?这就是接下来要学习的二叉查找树(BST)


    by @sunhaiyu

    2017.10.13

    转载于:https://www.cnblogs.com/sun-haiyu/p/7660753.html

    展开全文
  • 这一章节将讲解查找算法,包括顺序查找、二分查找。其中二分查找是通向编程高手路上的十大算法中的一种。 1 顺序查找 虫虫东东是兄弟俩,经常一起做游戏。这次他们玩的是猜数字。东东口袋中有10颗玻璃球,东东抓了...

    这一章节将讲解查找算法,包括顺序查找、二分查找。其中二分查找是通向编程高手路上的十大算法中的一种。

    1 顺序查找

    虫虫和东东是兄弟俩,经常一起做游戏。这次他们玩的是猜数字。东东口袋中有10颗玻璃球,东东抓了一把 (7颗),让虫虫猜手中有多少颗。东东只会告诉虫虫猜对了,太多了或者太少了。请问虫虫最多需要猜多少次才能猜中呢?
    我们想想可以怎么猜。
    如果从1,2,3开始按照顺序猜,那么就需要7次;
    如果是从10,9,8开始从大到小开始猜,就需要4次。
    如果随便乱猜 (随机猜),运气最好的时候只需要1次,运气最差需要猜10次。

    我们来分析一下,从小到大猜和从大到小猜其实是一回事儿:运气最好的时候只需要1次,运气最差需要猜10次。而随机乱猜的方法是不可取的,因为很难保证每次猜的数都不一样,即使能保证每次猜的数不一样,运气最差时仍然需要猜10次。既然这三种方法都一样,我们就用从小到大猜测的方式编写代码吧:

    int search (int n) //猜猜东东手中有几颗玻璃球 
    {
    	//从1开始,从小到大猜。数组的下标从0开始哦
    	for(int i = 0; i < size; i++)  
    	{
    		if(arr[i] == n)
    		{
    			return i; //猜到了就返回下标 
    		}
    	}
    	return -1; //所有数字都不对就返回-1 
    }
    

    这种方式称之为顺序查找。顺序查找是最简单的查找方式,适用于任何情况。运气最好的时候,时间复杂度为O(1);运气最差的时候,时间复杂度为O(N);平均下来这个方法的时间复杂度为O[(1 + 2 + 3 +… + n) / n] = O[n * (n + 1) / (2 * n)] = O[(n + 1) / 2] = O(N)。

    2 二分查找

    我们来想一想,是不是有更好的查找方法呢?10的一半是5,如果我们第一次猜5 (太小),那么1 ~ 5这5个数字就都排除掉了,剩下6 ~ 10这5个数字。第二次猜测8 (6与10的中间值,太大),就可以把8 ~ 10这三个数字排除掉。接下去只剩下6和7两个数了,我们先猜6 (太小),最后只剩下一个数字7。我们猜中了。这个方法一共猜了四次。这个方法貌似和刚才从大到小猜猜测的次数一样多嘛,这个方法有什么优势吗?
    运气最好的时候,这个方法只需要猜测1次,而运气最差的情况下,也仅仅需要猜测4次。不信?我们来看看下面的图:

    在这里插入图片描述
    这是一棵二叉树 (二叉树是什么东西?会结出好吃的水果吗?)。好吧,我以后再讲二叉树能不能结出水果的问题。现在只需要知道第一次猜最大值10和最小值1的平均值 (1 + 10) / 2 = 5.5,取5。第二次猜最大值10和最小值6的平均值 (6 + 10) / 2 = 8。第三次猜最大值7和最小值6的平均值 (6 + 7) / 2 = 6.5,取6。第四次猜最大值7和最小值7的平均值 (7 + 7) / 2 = 7。简单来说,就是每次猜最大值和最小值的平均值,如果猜对了,那就结束了;如果猜错了,忽略掉一半元素和刚刚猜的那个数之后,在剩余的数中继续猜。用这种猜法,5只需要猜1次就可以猜到,2和8只需猜2次,1, 3, 6, 9只需要猜3次,只有4、7和10需要猜4次。也就是说:这种方式最多也仅仅需要猜4次。可见这种方式的效率要比按顺序猜高了很多。

    上述猜数字的方法就是就是位列“十大算法”之一的二分查找。它的时间复杂度为O(logN)。如果把上述猜数字的游戏扩大到1100中猜一个数字,最多只需7次,效率比按顺序猜高14倍;11000中猜一个数字,最多只需10次,效率比按顺序猜高100倍。。。这么好的查找方式,是不是看着都有点激动呢?我们来看看二分查找的代码吧。二分查找有两种实现方式,分别是递归方式和迭代方式。先来看递归方式:

    //三个参数分别是:要查找的数,数组中要查找的范围。
    //low是最左边的元素的index,high是最右边的元素的index 
    int halfSearch (int n, int low, int high)
    {
    	if(low > high) //递归的出口1
    	{
    		return -1; //如果找不到要找的数,返回-1 
    	}
    	
    	//开始搜索
    	int middle = (low + high) / 2; //中间元素的下标
    	if(arr[middle] == n) //递归的出口2 
    	{
    		return middle; //返回的是找到的元素的下标 
    	}
    	else if(arr[middle] < n) //猜测的数比东东手中玻璃球的数量少 
    	{
    		//更新猜测范围:中间值、以及所有比中间值小的元素都不要了
    		low = middle + 1;  
    		return halfSearch(n, low, high); //递归搜索 
    	}
    	else //猜测的数比东东手中玻璃球的数量多 
    	{
    		//更新猜测范围:中间值、以及所有比中间值大的元素都不要了
    		high = middle - 1; 
    		return halfSearch(n, low, high); //递归搜索
    	}
    }
    

    我们知道递归的时候会占用大量内存,且有可能超出最大递归次数;而用迭代方式就不会出现这样的问题。因此实际使用的都是迭代版的实现:

    //三个参数分别是:要查找的数,数组中要查找的范围。
    //low是最左边的元素的index,high是最右边的元素的index 
    int halfSearch (int n, int low, int high)
    {
    	int middle = -1; //中间元素的下标,初始值为-1 
    	while(low <= high) //最左边的元素的下标一定比最右边的元素的下标小 
    	{
    		middle = (low + high) / 2; //中间元素的下标
    		if(arr[middle] == n)
    		{
    			return middle; //返回的是找到的元素的下标
    		}
    		else if(arr[middle] < n) //猜测的数比东东手中玻璃球的数量少
    		{
    			//更新猜测范围:中间值、以及所有比中间值小的元素都不要了
    			low = middle + 1;	
    		}
    		else //猜测的数比东东手中玻璃球的数量多
    		{
    			//更新猜测范围:中间值、以及所有比中间值大的元素都不要了
    			high = middle - 1;
    		}
    	}
    	return -1; //如果找不到要找的数,返回-1 
    }
    

    好了,我们看一下上面的代码是不是有问题:
    数学的角度看,middle = (low + high) / 2这行代码没有问题。但是从编程语言的角度看,low + high有可能超出C语言中int值的范围,所以需要在不改变意思的情况下修改代码。那么怎么改进呢,下面是三种改进方式,从数学的角度看,这三种方式是一样的。但是从编程语言的角度看,这三种方式是不一样的。我们分别进行讨论:
    1、middle = low / 2 + high / 2
    2、middle = low + (high - low) / 2
    3、middle = high + (low - high) / 2
    如果low和high都是奇数,例如1和5,middle应该等于3。第一种改进方式,middle = 1 / 2 + 5 / 2 = 0 + 2 = 2,得到错误的结果。
    第二种方式:无论哪种情况,都能得到正确的结果。可以采用这种改进方式。
    第三种方式:看上去跟第二种方式很相似。当low = 2,high = 5时,middle应该等于3,但是middle = 5 + (2 - 5) / 2= 5+ (-3) / 2 = 5 + (-1) = 4。得到错误的结果。

    综上所述,需要把middle = (low + high) / 2改成:middle = low + (high - low) / 2。

    下面是二分查找的最终代码:

    //三个参数分别是:要查找的数,数组中要查找的范围。
    //low是最左边的元素的index,high是最右边的元素的index 
    int halfSearch (int n, int low, int high)
    {
    	int middle = -1; //中间元素的下标,初始值为-1 
    	while(low <= high) //最左边的元素的下标一定比最右边的元素的下标小 
    	{
    		//middle = (low + high) / 2; 这种方式可能会导致数据超出int的范围
    		middle = low + (high - low) / 2 //计算中间元素的下标
    		if(arr[middle] == n)
    		{
    			return middle; //返回的是找到的元素的下标
    		}
    		else if(arr[middle] < n) //猜测的数比东东手中玻璃球的数量少
    		{
    			//更新猜测范围:中间值、以及所有比中间值小的元素都不要了
    			low = middle + 1;	
    		}
    		else //猜测的数比东东手中玻璃球的数量多
    		{
    			//更新猜测范围:中间值、以及所有比中间值大的元素都不要了
    			high = middle - 1;
    		}
    	}
    	return -1; //如果找不到要找的数,返回-1 
    }
    

    上面说了二分查找的那么大的优势,这里不能不提醒一下,二分查找对被查找的数组是有要求的:所有元素必须是有序的。如果数组中的元素的次序是乱的,那就没法用二分查找了,只能用顺序查找。如果这个数组只查找一次,那就用顺序查找吧,时间复杂度为O(N)。如果这个数组会被查询多次,那么我就建议先对数组中的元素进行排序,然后再用二分查找。排序算法的时间复杂度为O(N * log N)。虽然前面花了很多时间,但是正所谓“磨刀不误砍柴工”,后面的查找就要比顺序查找快多了,多次查找之后,总的效率会提高不少。

    二分查找中最重要的思想就是“二分”,也就是:middle = low + (high - low) / 2。如果把这个公式换成:middle = low + (key - a[low]) * (high - low) / (a[high] - a [low]),二分查找就变成了插值查找。插值查找对于分布比较均匀的数组查找效率比较高,但对于分布极端不均匀的数组,效率反而降低。最关键的是,当a[high] - a [low] = 0时,分母变成0,所以插值查找算法是有缺陷的,确切的说,它是有限制条件的。而二分查找没有这些问题,且效率十分稳定,因此二分查找是最常用的查找算法。

    最后,我想说一下,“二分查找”这个名字取的名不符实。该算法在获取数组的中间值之后,实际上是把数组分成三部分,而不是两部分。以下面1 ~ 8这8个数字为例,数组被分为:左边部分 (1 ~ 3)、中间的值 (4)、右边部分 (5 ~ 8)。类似的情况在快速排序中也会出现。不过这仅仅是名字上的问题,不影响我们对算法本身的理解。

    在这里插入图片描述

    思考一个问题:如果要在一个从小到大有序的数组arr中找第k大的数,则arr[k - 1]就是要的那个数。但是如果数组arr中的数据不是有序的,我们该怎么办呢?
    我先提出三种思路:
    1、参考选择排序:从n个数中顺序查找,找到最大值,然后把这个最大值去掉。然后继续在剩下n - 1个数中顺序查找,找到最大值。这样重复k次,就可以得到第k大的元素了。这样做的时间复杂度为O(N * K)。
    2、对这n个数从大到小排序,然后第k - 1个数就是第k大的值。排序的时间复杂度为O(N * logN),求第n - 1个数的时间复杂度为O(1),所以总的时间复杂度为O(N * logN)。如果使用桶排序,时间复杂度可以降低到O(N),但是桶排序存在一些问题,这里暂且不讨论。这个实现方法需要排序算法,请查阅排序章节后再实现这个功能。
    3、进行部分排序:借助于堆排序,建立一个有k个数组成的小顶堆。然后遍历剩余元素,跳过比堆顶元素小的数,如果被遍历的元素比堆顶元素大,就用这个数取代堆顶元素,并重新维护这个堆。这样做的时间复杂度为O((N- k) * logK),如果k远小于n,则时间复杂度 = O(N * logK)。这个代码在扩展篇中已经实现了,请前往扩展篇中查阅。

    聪明的读者,你还能想到更快的方法吗?“线性查找”算法可以把top k问题的时间复杂度降低到O(N)。请区分一下,这里所说的是“线性查找”,而不是上面已经介绍过的“顺序查找”。
    由于线性查找算法需要用到插入排序算法和快速排序的划分思想,我们就把它放在扩展篇中介绍。

    3 扩展

    在数组中使用二分查找确实可以非常高效的找到数据,但是如果被查找的数据是不固定的 (可能会动态的增加、删除数据),这时如果还是用数组进行储存数据就显得不太合适了。因为在数组中增加、删除数据的时间复杂度为O(N)。添加数据之后再进行查找,时间复杂度为O(N + logN),效率就变得很低。针对这种情况,科学家们设计了二叉查找树。二叉查找树的内容我们将在“树”这个章节中进行介绍。

    最后,我们再介绍一种散列表查找,我们暂时称之为“地图”吧,请跟数据结构中的“图”区分开。例如,打仗时,指挥官不会自己跑到要被轰炸的地方,高喊着“向我开炮”,而是会在指挥部,用手指着地图上的某一个点,让士兵发射炮弹到这个位置。士兵们就可以对这个点进行精确打击。为什么这样是可行的呢?原因是地图上的某一个点与地球上某一个位置是一一对应的。只要知道地图上某一个点的位置,就可以算出地球上对应位置的坐标。这种数据结构可以把两个看似毫不相关的数据关联在一起。地图上的一个点称之为key,地球上某一个实际位置称之为value。key <–> value这两个数据往往是一起使用的,称之为“键值对”。这种数据结构用的比较多,有趣的是它在不同的语言中有不同的叫法,例如Java中称之为HashMap、HashTable;C#中叫Dictionary;Python中则称之为字典。恰当地使用这种数据结构可以极大地提高编程效率,降低代码复杂度。这里就不详细介绍这个算法的实现方式了。

    关于查找算法就到这里吧。其它的查找算法,例如Fibonacci查找、字典树、多路查找树等查找算法用的相对较少,请有兴趣的朋友查看参考书吧。

    4 思考

    如果有1000个人同时在10亿个数据中进行查找,怎样才能保证每个人都能在很短时间里得到自己想要的结果?

    展开全文
  • 顺序查找:对表中的元素排序无要求,但如果表中各个元素的查找概率并不相等,则应先元素的查找概率进行排序,使表中元素的查找概率由小到大重新排列,以便提高查找概率。 二分法查找:折半查找的效率比顺序查找高...

    顺序查找:对表中的元素排序无要求,但如果表中各个元素的查找概率并不相等,则应先对元素的查找概率进行排序,使表中元素的查找概率由小到大重新排列,以便提高查找概率。

    二分法查找:折半查找的效率比顺序查找高,但折半查找只适用于有序表,且限于顺序存储结构(对链式存储无效)。


    /**
    * 顺序查找法
    * @param $val 要查找的值
    */
    function query_search($array,$val)
    {
    foreach ($array as $k => $v)
    {
    if($v == $val)
    {
    return $k ;
    }
    }

    return -1 ;
    }

    /**
    * 顺序查找法
    * @param $val 要查找的值 $arr 数据源 $low 其实位置 $top 数组大小
    */
    function bin_search($arr,$low,$top,$val)
    {
    if ($low <= $top) {
    $mid = floor(($low + $top) / 2);
    if ($arr[$mid] == $val) {
    return $mid;
    } elseif ($arr[$mid] < $target) {
    return bin_search($arr, $mid + 1, $top, $target);
    } else {
    return bin_search($arr, $low, $top - 1, $target);
    }
    } else {
    return -1;
    }
    }
    // 查找的源数组
    $array = array(1,2,4,7,5,6,3,8);

    $n = query_search($array,2);
    echo "顺序查找位置->".$n."<br>";
    sort($array);
    $num = bin_search($array,0,count($array)-1,2);
    echo "二分查找位置->".$num;

    转载于:https://www.cnblogs.com/yelons/p/6524722.html

    展开全文
  • 符号表符号表是一种存储键值的数据结构,支持两种操作:插入(put)查找(get)。 可以分为无序符号表有序符号表...无序链表中的顺序查找非常的低效 向一个空表插入N个不同的键需要N^2/2次比较。 只适用于小型

    符号表

    符号表是一种存储键值对的数据结构,支持两种操作:插入(put)和查找(get)。
    可以分为无序符号表和有序符号表。

    本节的实现基于

    每个键只对应着一个值,表不允许存在重复的键
    向表中存入新的键值对和已有的键冲突时,新的值会替代旧的值
    键不能为空null
    值不能为空null

    无序链表中的顺序查找

    非常的低效
    向一个空表插入N个不同的键需要N^2/2次比较。

    只适用于小型问题,对于大型符号表很慢

    public class SequentialSearchST<Key,Value>{
        private Node first;  // 链表首结点
        private class Node{
            Key key;
            Value val;
            Node next;
            public Node(Key key, Value val, Node next){
                this.key = key;
                this.val = val;
                this.next = next;
            }
        }
        public Value get(Key key){
            for(Node x = first; x != null; x = x.next){
                if(key.equals(x.key))
                    return x.val;
            }
            return null;
        }
        public void put(Key key, Value val){
            for(Node x = first; x != null; x = x.next){
                if(key.equals(x.key)){
                    x.val = val;
                    return ;
                }
            }
            first = new Node(key, val, first); // 放在首结点位置(链表)
        }
    }

    有序数组的二分查找

    rank() 是核心
    除了符号表的get/put等关键操作,还基于有序的数组实现其它方法

    最优的查找效率和空间需求,进行有序性相关的操作。但是插入操作很慢
    注:
    有序数组在插入时就进行了排序。

    package com.base;
    
    public class BinarySearchST<Key extends Comparable<Key>, Value> {
        private static final int INIT_CAPACITY = 2;
        private Key[] keys;
        private Value[] vals;
        private int N = 0;
    
        // 默认容量初始化
        public BinarySearchST() { this(INIT_CAPACITY); }   
    
        // 给定容量初始化
        public BinarySearchST(int capacity) { 
            keys = (Key[]) new Comparable[capacity]; 
            vals = (Value[]) new Object[capacity]; 
        }   
    
        // 调整数组大小
        private void resize(int capacity) {
            assert capacity >= N;
            Key[]   tempk = (Key[])   new Comparable[capacity];
            Value[] tempv = (Value[]) new Object[capacity];
            for (int i = 0; i < N; i++) {
                tempk[i] = keys[i];
                tempv[i] = vals[i];
            }
            vals = tempv;
            keys = tempk;
        }
    
    
        // 是否包含
        public boolean contains(Key key) {
            return get(key) != null;
        }
    
        // 键值对个数
        public int size() {
            return N;
        }
    
        // 符号表是否为空
        public boolean isEmpty() {
            return size() == 0;
        }
    
        // 根据键得到值
        public Value get(Key key) {
            if (isEmpty()) return null;
            int i = rank(key); 
            if (i < N && keys[i].compareTo(key) == 0) return vals[i];
            return null;
        } 
    
        // 返回比跟定键小的键
        public int rank(Key key) {
            int lo = 0, hi = N-1; 
            while (lo <= hi) { 
                int m = lo + (hi - lo) / 2; 
                int cmp = key.compareTo(keys[m]); 
                if      (cmp < 0) hi = m - 1; 
                else if (cmp > 0) lo = m + 1; 
                else return m; 
            } 
            return lo;
        } 
    
    
        // 更新值,或插入键值
        public void put(Key key, Value val)  {
            if (val == null) { delete(key); return; }
    
            int i = rank(key);
    
            // key is already in table
            if (i < N && keys[i].compareTo(key) == 0) {
                vals[i] = val;
                return;
            }
    
            // 扩展keys
            if (N == keys.length) resize(2*keys.length);
    
            for (int j = N; j > i; j--)  {
                keys[j] = keys[j-1];
                vals[j] = vals[j-1];
            }
            keys[i] = key;
            vals[i] = val;
            N++;
        } 
    
    
        // 删除键值对
        public void delete(Key key)  {
            if (isEmpty()) return;
    
            // compute rank
            int i = rank(key);
    
            // key not in table
            if (i == N || keys[i].compareTo(key) != 0) {
                return;
            }
    
            for (int j = i; j < N-1; j++)  {
                keys[j] = keys[j+1];
                vals[j] = vals[j+1];
            }
    
            N--;
            keys[N] = null;  // to avoid loitering
            vals[N] = null;
    
            // resize if 1/4 full
            if (N > 0 && N == keys.length/4) resize(keys.length/2);
    
        } 
    
        // 删除最小键和关联的值
        public void deleteMin() {
            if (isEmpty()) throw new RuntimeException("Symbol table underflow error");
            delete(min());
        }
    
        // 删除最大键和关联的值
        public void deleteMax() {
            if (isEmpty()) throw new RuntimeException("Symbol table underflow error");
            delete(max());
        }
    
    
       /*****************************************************************************
        *  Ordered symbol table methods
        *  有序符号表的方法
        *****************************************************************************/
        // 最小
        public Key min() {
            if (isEmpty()) return null;
            return keys[0]; 
        }
        // 最大
        public Key max() {
            if (isEmpty()) return null;
            return keys[N-1];
        }
        // 排名在k的键
        public Key select(int k) {
            if (k < 0 || k >= N) return null;
            return keys[k];
        }
        // 小于等于key的最大键
        public Key floor(Key key) {
            int i = rank(key);
            if (i < N && key.compareTo(keys[i]) == 0) return keys[i];
            if (i == 0) return null;
            else return keys[i-1];
        }
        // 大于等于key的最小键
        public Key ceiling(Key key) {
            int i = rank(key);
            if (i == N) return null; 
            else return keys[i];
        }
        // lo--hi 之间的键的数量
        public int size(Key lo, Key hi) {
            if (lo.compareTo(hi) > 0) return 0;
            if (contains(hi)) return rank(hi) - rank(lo) + 1;
            else              return rank(hi) - rank(lo);
        }
        // 迭代
        public Iterable<Key> keys() {
            return keys(min(), max());
        }
    
        public Iterable<Key> keys(Key lo, Key hi) {
            Queue<Key> queue = new Queue<Key>(); 
            if (lo == null && hi == null) return queue;
            if (lo == null) throw new RuntimeException("lo is null in keys()");
            if (hi == null) throw new RuntimeException("hi is null in keys()");
            if (lo.compareTo(hi) > 0) return queue;
            for (int i = rank(lo); i < rank(hi); i++) 
                queue.enqueue(keys[i]);
            if (contains(hi)) queue.enqueue(keys[rank(hi)]);
            return queue; 
        }
    }
    展开全文
  • 查找:在相同类型的记录构成的集合中找出满足给定条件的记录 ...集合{线性表:适用于静态查找,顺序查找、折半查找等技术树表:适用于动态查找,二叉排序树的查找技术散列表:静态查找和动态查找均适用,
  • 顺序查找通常分为一般的无序线性表的顺序查找和对按关键字有序的顺序表的顺序查找。下面分别进行讨论。 1.1、一般线性表的顺序查找 作为一种最直观的查找方法,其基本思想是从线性表的一端开始,逐个检查关键字...
  • 最近总结了各大排序算法的原理 ,并其进行了实现,想着一并把查找算法总结了,今天就着手開始总结查找算法。 废话不多说。这篇文章从最简单的查找算法開始讲起。之后会补充复杂的二叉搜索树查找(BST)B树,B+...
  • 顺序查找对于有序序列/链表无序序列/链表都可行,但二分查找就只能有序序列进行查找了。二分查找在查找时速度较快(lgN),不过它序列的有序要求会导致节点插入时间的增加(相对无序序列/链表)。  《算法》...
  • 符号表表示一张抽象的表格,我们将信息存储到其中,然后按照指定的键来搜索并获取这些信息。键值的具体意义取决于不同的应用。符号表中可能会保存很多键很多信息,因此...查找( get ),即根据给定的键得到相应
  • 问题的提出:编写程序数据序列采用二分查找和顺序查找法查找元素的下标,要求使用类模板实现(其中二分法查找算法要求用递归实现,给定数据序列有序)。
  •  本文为查找算法的第一部分内容,包括了基本概念,顺序查找、二分查找和索引查找。关于散列表和B树查找的内容,待有空更新吧。 基本概念  查找(search)又称检索,在计算机上数据表进行查找,就是根据所给...
  • ②二分查找/折半查找; ③插值查找; ④斐波那契查找(黄金分割点查找); 二、顺序(线性)查找 1、说明 顺序无要求; 2、代码实现 package com.zb.ds.search; //顺序查找 public class SeqSearch {...
  • 顺序查找,二分查找

    2013-06-19 10:56:37
    同时这种查找思想也适合于对顺序表数据结构链表数据结构中的元素进行查找。它的缺点在于平均查找长度过大,查找效率较低。 例: #include using namespace std; typedef struct student{ int
  • 3 对分和顺序

    2020-05-26 19:24:17
    写出两种检索算法:在一个排好序的数组T[1…n]中查找x...对分查找适用于顺序存储结构且关键字有序排列的情况。首先,将数组中间位置记录的关键字与查找关键字比较,若两者相等,则查找成功。否则利用中间位置记录将...
  • 查找:从一组数据集合中找出符合要求的数据,这个过程称为查找,有两种情况,查找成功和查找失败 查找表:用于查找的数据集合称为查找表,由同一种数据类型组成。可以是数组或链表等数据类型。一般包括四种操作:增...
  • 符号表是一种存储键值的数据结构,支持两种操作插入查找,就是将一组新的键值存入表中然后根据给定的键得到对应的值,在编程语言中常用Dictionary原理类似。符号表是一种典型的抽象数据...无序链表的顺序查找 ...
  • 线性查找(Linear Search)又称顺序查找,是一种最简单的查找方法,它的基本思想是从第一个记录开始,逐个比较记录的关键字,直到给定的K值相等,则查找成功;若比较结果与文件中n个记录的关键字都不等,则查找...
  • C语言顺序表顺序查找和折半查找的基本思想和应用 顺序查找算法:又称为线性查找,主要用在—线性表—中进行查找 通常分为:1—无序线性表的一般查找; 2—关键字有序的顺序表查找; 优缺点分析: 缺点:当线性表的...
  • 顺序查找基本思想属于线性查找和无序查找,从一端开始顺序扫描,直到找到与目标值value相等的元素。这是最基本的查找方法,也是时间复杂度最高的查找算法。在数据过多时,这种方法并不适用。代码实现分块查找基本...
  • 顺序查找

    2017-02-26 19:27:26
    //顺序查找和折半查找(又称二分查找) //没有排序的数据用顺序查找(简单但速度慢) //已排序的数据用二分查找 #include &lt;iostream&gt; using namespace std; int SequentialSearch(int *list,...
  • 无序链表中的顺序查找 实现 性能 有序数组中的二分查找 实现 性能 现代计算机网络使人们能够访问海量的信息,而且各种计算设备正在源源不断地生成新的信息,高效检索这些信息的能力就成了处理它们的重要...
  • 分查找和递归

    2019-06-29 07:30:09
    分查找法是一组有序的数字中进行查找,传递相应的数据,进行比较查找到与原数据相同的数据,查找到了返回对应的数组下标,没有找到返回-1; 如下示例,其中有序数组中, 是按照从小到大的顺序排列的。(再次感谢...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 758
精华内容 303
关键字:

对分查找和顺序查找