`
mvj3
  • 浏览: 24741 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

二分查找和插入

    博客分类:
  • ruby
阅读更多
# 二分查找(又称折半查找)是在一个有序表里查找元素的复杂度为O(log(n))的算法。先从中# 二分查找(又称折半查找)是在一个有序表里查找元素的复杂度为O(log(n))的算法。先从中间位置开始比较,相等则返回,如小于中间值,则将接下来的查找范围设定为前一子表,大于则为后一子表,以下如此类推。
# 维基百科参考:http://en.wikipedia.org/wiki/Binary_search_algorithm
class Array
  # 迭代版本
  def binary_search_in_iterative num, insert = true
    min, max = 0, self.size - 1
    while min <= max
      mid =  (min + max) / 2
      if num < self[mid]
        max = mid - 1
      elsif num == self[mid]
        return mid
      else
        min = mid + 1
      end
    end

    insert_item num, min, mid if insert
    return nil if min > max
  end

  # 递归版本
  def binary_search_in_recursive num, insert = true, min = nil, max = nil
    min ||= 0
    max ||= self.size - 1
    mid = (min + max) / 2

    if min > max
      insert_item num, min, mid if insert
      return nil
    end

    if num > self[mid]
      binary_search_in_recursive num, insert, mid + 1 , max
    elsif num < self[mid]
      binary_search_in_recursive num, insert, min, mid - 1
    else
      return mid
    end
  end

  def insert_item num, min, mid
    min = mid if self[min].nil?
    self[min..min] = (self[min] < num) ? [self[min], num] : [num, self[min]]
  end
end



require 'benchmark'

array = (0..6**7).to_a

puts "数组是从0到#{array[-1]}的之间的所有整数"
[-1, -6**3, 0, 4**5, 6**6].each do |num|
  puts "匹配#{num}"
  Benchmark.bm do |x|
    x.report("index    ") { array.index num }
    x.report("iterative") { array.binary_search_in_iterative num, false }
    x.report("recursive") { array.binary_search_in_recursive num, false }
  end
  puts
end


__END__
以下是运行本程序的结果


数组是从0到279936的之间的所有整数
匹配-1
      user     system      total        real
index      0.010000   0.000000   0.010000 (  0.014947)
iterative  0.000000   0.000000   0.000000 (  0.000048)
recursive  0.000000   0.000000   0.000000 (  0.000065)

匹配-216
      user     system      total        real
index      0.010000   0.000000   0.010000 (  0.014744)
iterative  0.000000   0.000000   0.000000 (  0.000028)
recursive  0.000000   0.000000   0.000000 (  0.000040)

匹配0
      user     system      total        real
index      0.000000   0.000000   0.000000 (  0.000005)
iterative  0.000000   0.000000   0.000000 (  0.000019)
recursive  0.000000   0.000000   0.000000 (  0.000032)

匹配1024
      user     system      total        real
index      0.000000   0.000000   0.000000 (  0.000059)
iterative  0.000000   0.000000   0.000000 (  0.000031)
recursive  0.000000   0.000000   0.000000 (  0.000048)

匹配46656
      user     system      total        real
index      0.000000   0.000000   0.000000 (  0.003513)
iterative  0.000000   0.000000   0.000000 (  0.000022)
recursive  0.000000   0.000000   0.000000 (  0.000045)


从上面可以看到,迭代都比递归快一倍左右,不难看出Ruby里默认的数组查找是直接在线性时间里遍历查找的,查看Array#index对应的C源码一看便知。


static VALUE
rb_ary_index(argc, argv, ary)
    int argc;
    VALUE *argv;
    VALUE ary;
{
    VALUE val;
    long i;

    if (argc  == 0) {
	RETURN_ENUMERATOR(ary, 0, 0);
	for (i=0; i<RARRAY(ary)->len; i++) {
	    if (RTEST(rb_yield(RARRAY(ary)->ptr[i]))) {
		return LONG2NUM(i);
	    }
	}
	return Qnil;
    }
    rb_scan_args(argc, argv, "01", &val);
    for (i=0; i<RARRAY(ary)->len; i++) {
	if (rb_equal(RARRAY(ary)->ptr[i], val))
	    return LONG2NUM(i);
    }
    return Qnil;
}
分享到:
评论

相关推荐

    易语言源码二分插入排序.rar

    总的来说,学习并实践这个易语言源码二分插入排序,不仅可以加深对二分查找和插入排序的理解,还能提升在易语言环境下的编程能力。这对于想要掌握易语言或者对排序算法感兴趣的开发者来说,是一个很好的学习资源。

    JS实现二分插入排序,前端必会

    二分插入排序是一种在计算机科学中用于对数组或列表进行排序的算法,它结合了二分查找和插入排序的优点。在前端开发中,理解和掌握这种排序算法对于优化数据处理和提高程序性能至关重要。以下是关于JS实现二分插入...

    java二分查找插入法

    注意,实际的Java代码中并没有提供完整的二分查找插入法实现,只是给出了一个实现了Comparable接口的Bean类,这需要开发者自己补充二分查找和插入操作的代码。 在实际应用中,除了基本的数组或列表,还可以使用Java...

    深入理解二分查找(一、二分查找及其变体)

    4. **二分查找插入位置**:用于在有序数组中找到新元素的合适插入位置,保持数组有序。 5. **存在性二分查找**:只关心目标元素是否存在,不需要返回具体位置。 6. **查找最近值**:当目标元素不存在时,返回最接近...

    查找算法集(顺序查找、二分查找、插值查找、动态查找)

    以下是四种常见的查找算法:顺序查找、二分查找、插值查找和动态查找。 顺序查找 顺序查找是一种最简单的查找算法,它的实现方式是从数组或链表的第一个元素开始,逐个比较元素直到找到目标元素或达到数组或链表的...

    二分查找解题

    例如,在大型数据集的查找、插入和删除操作中,结合排序和二分查找可以极大地提高效率。 总的来说,二分查找是一种高效且优雅的算法,它的递归实现进一步体现了编程中的抽象和简化思维。通过理解并掌握二分查找,...

    VB 二分查找

    然而,如果数据未排序或经常需要插入和删除元素,二分查找可能不是最佳选择,因为这些操作会破坏已排序的顺序。 ### 5. 扩展讨论 - **变种与优化**:二分查找可以进行一些变种,例如对链表的二分查找,或者在有...

    C++ 二分查找法

    此外,对于非静态数据集,如频繁插入或删除元素的情况,需结合其他数据结构(如平衡二叉树)来保持数据有序性,以确保二分查找的高效性。 #### 五、总结 通过以上分析,我们了解到C++中二分查找法的实现细节及其...

    模拟实验-C#版基于二分查找的稳定“插入排序”算法

    这有助于我们了解在实际应用中,二分查找插入排序与冒泡排序在处理相同数据集时的速度差异。 总的来说,这个实验提供了一个深入理解和实践排序算法的平台,特别是如何利用二分查找优化插入排序的过程。通过对C#代码...

    二分查找和hash表的实现

    二分查找和哈希表是两种在计算机科学中广泛使用的数据结构和算法,它们在解决查找和检索问题时有着高效的表现。这篇文档将深入探讨这两种技术的原理、实现及应用场景。 首先,我们来讨论二分查找。二分查找,也称为...

    二分查找算法FLASH演示

    2. 二分查找插入位置:除了查找特定值,还可以用于找到一个新元素的合适插入位置,保持数组有序。 3. 二分查找在平衡二叉搜索树中:二分查找的概念也被应用于二叉搜索树,特别是自平衡树如AVL树和红黑树。 六、实际...

    二分查找的C实现

    二分查找,也称为折半查找,是一种在有序数组中搜索特定元素的高效算法。它的基本思想是将数组分成两半,然后根据目标值与中间元素的比较结果,决定是在左半部分还是右半部分继续查找。这个过程不断进行,直到找到...

    二分查找代码

    二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表...

    对数组进行二分查找

    - 二分查找的空间复杂度通常为 O(1),因为它只需要几个额外的变量来存储指针和中间索引,不随输入大小增加。 5. **适用场景**: - 二分查找适用于已排序的数组,且数组需要保持排序状态。在无序数组中使用二分...

    查找算法:二分查找、顺序查找

    这里我们将深入探讨两种常见的查找算法:二分查找和顺序查找。 **一、顺序查找** 顺序查找是最基础的查找算法之一。它的工作原理是从数据集(如数组或列表)的第一个元素开始,逐个比较目标值与当前元素,直到找到...

    二分查找和二叉排序树(C++实现)

    二分查找和二叉排序树是计算机科学中两种重要的数据结构和算法,它们在处理大量数据时具有高效性。下面将详细介绍这两种概念及其C++实现的关键点。 首先,二分查找是一种在有序数组中查找特定元素的搜索算法。其...

    java二分查找算法

    ### Java二分查找算法知识点详解 #### 一、二分查找算法概述 二分查找算法是一种在有序数组中查找特定元素的搜索算法。...对于开发者来说,理解和掌握二分查找算法的实现细节对于提高程序性能具有重要意义。

    二分查找算法的C语言版

    ### 二分查找算法的C语言实现 #### 算法概述 二分查找算法(Binary Search)是一种在有序数组中查找特定元素的高效算法。它的工作原理是将目标值与数组中间位置的元素进行比较,如果相等,则查找成功;如果不相等,...

    Java 二分查找 算法

    二分查找算法不仅可以用于查找,还可以进行一些变体操作,如插入、删除和查找最近的元素等。在高级数据结构如平衡二叉搜索树(AVL 树、红黑树等)中,二分查找的概念也被广泛运用。理解并熟练掌握二分查找算法对于...

    折半插入排序算法.txt

    折半插入排序通过结合二分查找和插入排序的优点,提高了排序效率,尤其是在处理小规模数据集时效果更佳。虽然在最坏情况下仍具有较高的时间复杂度,但在实际应用中往往能展现出较好的性能表现。

Global site tag (gtag.js) - Google Analytics