查找，最天真无邪的方法就是linearSearch：将给定的数组arr从头至尾扫描一遍
int linearSearch(int arr[],int n,int x)
{
int i;
for(i=0;i<n;i++)
{
if(x==arr[i])
return i;
}
return -1;
}
毫无疑问，该算法的时间复杂度为O(n).
另外，倘若所给的是一个有序的数组arr，那么我们可以考虑折半查找：
1) 将待查找元素x与arr中间元素比较
2) 相等则返回index
3) 小于则抛弃右半部分
4) 大于则抛弃左半部分
这是递归实现的版本
int binarySearch(int arr[],int l,int r,int x)
{
if(l<=r)
{
int mid=(l+r)/2;
if(x==arr[mid])
{
return mid;
}else if(x<arr[mid])
{
return binarySearch(arr,l,mid-1,x);
}else{
return binarySearch(arr,mid+1,r,x);
}
}
return -1;
}
这是循环迭代实现的版本
int binarySearch2(int arr[],int l,int r,int x)
{
int mid;
while(l<=r)
{
mid=(l+r)/2;
if(x==arr[mid])
{
return mid;
}else if(x<arr[mid])
{
r=mid-1;
}else{
l=mid+1;
}
}
return -1;
}
折半查找的时间复杂度为O（Logn）.
还有一种内插搜索算法,它的平均时间复杂度为O(LogLogn)，但最坏情况是O(n).
int interpolationSearch(int arr[],int n,int x)
{
int l=0;
int r=n-1;
int m;
while(arr[r]!=arr[l]&&x>=arr[l]&&x<=arr[r])
{
m=l+((x-arr[l])*(r-l)/(arr[r]-arr[l])); /*这里应该是数学家讨论的问题*/
if(arr[m]<x)
{
l=m+1;
}
else if(x<arr[m])
{
r=m-1;
}
else
{
return m;
}
}
if(x==arr[l])
{
return l;
}
else{
return -1;
}
}
<!--EndFragment-->
相关推荐
查找算法比较 查找算法是计算机科学中的一种基本算法，用于搜索特定的数据元素在数据结构中的位置。查找算法的性能对整个系统的效率和可靠性都有着至关重要的影响。本文比较了顺序查找、折半查找和分块查找这三种...
比较在有序表和无序表下进行顺序查找时的效率 表中的奇数从1开始一共n个，要查找searches次 1.生成新的有序表 2.生成新的无序表 3.测试查找有序表的效率 4.测试查找无序表的效率 比较在同一有序表下进行顺序查找...
在众多的搜索算法中，折半查找算法因其简单高效而被广泛应用。然而，随着数据量的不断增长，传统折半查找算法的性能在某些场合下已不能完全满足需求。本文将针对这一问题，探讨折半查找算法的改进方法，并给出相应的...
二分查找算法 二分查找算法是一种高效的查找算法，适用于已经排好序的数组或链表中查找特定的元素。该算法的时间复杂度为O(log n)，远远优于顺序查找算法的O(n)。 二分查找算法的基本思想是将数组或链表分成两个...
本实验主要探讨了三种基本的查找算法：顺序查找、折半查找（二分查找）和索引查找，这些算法都是在数组或集合中寻找特定元素的重要方法。下面将详细解释这三种查找算法，并结合C语言编程环境进行深入分析。 1. **...
顺序查找是一种最简单的查找算法，它的实现方式是从数组或链表的第一个元素开始，逐个比较元素直到找到目标元素或达到数组或链表的末尾。顺序查找的时间复杂度为O(n)，其中n是数组或链表的元素个数。 在给定的代码...
查找算法的比较 在计算机科学中，查找算法是一种基本且常用的算法，它们的应用非常广泛。本文将对几种常用的查找算法进行比较，包括顺序查找、二分查找、二叉树查找和哈希表查找。 顺序查找是一个最简单的查找算法...
顺序查找是一种简单的查找算法，通过从数组的第一个元素开始，逐个比较元素直到找到目标元素或到达数组的末尾。其时间复杂度为 O(n)。 2. 二分查找（Binary Search） 二分查找是一种高效的查找算法，对于已经...
实验8的查找算法比较报告主要涉及七种不同的查找方法，分别是顺序查找、二分查找、插值查找、斐波那契查找、树表查找、分块查找和哈希查找。这些算法在计算机科学中用于在数据集合中寻找特定元素。 **查找的概述** ...
在IT领域，查找算法是计算机科学中的核心概念，特别是在数据结构和算法设计中。本文将深入探讨《C++查找算法大集锦》中所涵盖的各种查找技术，包括差值查找法、斐波那契查找、哈希查找（拉链法与探测法）以及顺序和...
折半查找算法的基本思想是将整个查找区间分为两半，然后通过比较中间元素与要查找的元素的大小关系来确定下一步的查找方向。如果要查找的元素小于中间元素，则继续在左半区间查找，否则继续在右半区间查找。重复这个...
平均查找长度（ASL）是衡量查找性能的重要指标，代表查找算法在查找成功时的平均比较次数，与查找集合中的记录个数概率分布有关。在等概率情况下，ASL可以通过求和公式计算得出。 线性查找是基于顺序查找技术的，其...
数据结构中的查找算法是计算机科学中的重要组成部分，它涉及到如何高效地在大量数据中寻找特定信息。查找操作，也就是检索，通常在数据元素的集合，即查找表中进行。查找的效率与查找对象的组织方式和所采用的查找...
在数据结构的学习和应用中，查找算法是基本而重要的组成部分。本文将深入探讨C语言中几种常见的查找算法，帮助理解它们的原理、特点及应用场景。 一、静态查找 在数据结构中，静态查找主要是针对已经排序的数据...
在计算机科学中，查找算法是数据结构和算法领域中的核心概念，用于在数据集合中寻找特定元素。这里我们将深入探讨两种常见的查找算法：二分查找和顺序查找。 **一、顺序查找** 顺序查找是最基础的查找算法之一。它...
在IT领域，尤其是在编程中，理解并掌握不同的查找算法是至关重要的。本文将详细解析C#中的基础查找算法，包括静态查找与动态查找、内查找与外查找，以及两种具体的查找算法：顺序查找（线性查找）和二叉查找（折半...
这篇实验报告，来源于云南大学数据结构课程的第七次实践，聚焦于查找算法的理论和实现，特别是哈希表这一高效的数据结构。哈希表，也称为散列表，是一种能够实现快速查找的结构，它通过哈希函数将数据映射到一个固定...
### 区间表的快速查找算法 #### 一、引言 在许多应用领域中，尤其是在涉及大量数据处理的行业中，比如电信业，高效的查找算法是确保系统性能的关键因素之一。传统的查找方法如折半查找虽然简单易实现，但在面对大...
查找算法是数据结构和算法中的重要组成部分，用于在数据集合中寻找特定元素。本篇文章将详细探讨如何用C语言设计查找算法，以及二叉排序树（Binary Search Tree, BST）的相关操作。 首先，我们来理解一下什么是二叉...