c 语言 三元搜索 - 迭代与递归(Ternary Search)

2024-03-25 12:20

本文主要是介绍c 语言 三元搜索 - 迭代与递归(Ternary Search),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

        计算机系统使用不同的方法来查找特定数据。有多种搜索算法,每种算法更适合特定情况。例如,二分搜索将信息分为两部分,而三元搜索则执行相同的操作,但分为三个相等的部分。值得注意的是,三元搜索仅对排序数据有效。在本文中,我们将揭开三元搜索的秘密——它是如何工作的,为什么它在某些情况下更快。无论您是编码专家还是刚刚起步,都准备好快速进入三元搜索的世界!
什么是三元搜索?
        三元搜索是一种搜索算法,用于查找排序数组中目标值的位置。它的工作原理是将数组分为三部分,而不是像二分搜索那样分为两部分。基本思想是通过将目标值与将数组分为三个相等部分的两个点上的元素进行比较来缩小搜索空间。
        mid1 = l + (rl)/3 
        mid2 = r – (rl)/3 
三元搜索的工作原理:
        这个概念涉及将数组分成三个相等的段,并确定关键元素(正在寻找的元素)位于哪个段。它的工作原理与二分搜索类似,不同之处在于通过将数组分为三部分而不是两部分来降低时间复杂度。

以下是三元搜索工作的分步说明:
1、初始化:
        从排序数组开始。
        设置两个指针left和right,最初指向数组的第一个和最后一个元素。
2、划分数组:
        计算两个中点mid1和mid2,将当前搜索空间分为三个大致相等的部分:
                mid1 = 左 + (右 – 左) / 3
                mid2 = 右 – (右 – 左) / 3
        该数组现在有效地分为[left, mid1]、(mid1, mid2 ) 和[mid2, right]。
3、与目标比较: .
        如果target等于mid1或mid2处的元素,则查找成功,并返回索引
        如果目标小于mid1处的元素,则将右指针更新为mid1 – 1。
        如果目标大于mid2处的元素,则将左指针更新为mid2 + 1。
        如果目标位于mid1和mid2的元素之间,则将左指针更新为mid1 + 1,将右指针更新为mid2 – 1。
4、重复或结论:
        使用缩小的搜索空间重复该过程,直到找到目标或搜索空间变空。
        如果搜索空间为空并且未找到目标,则返回一个值,指示目标不存在于数组中。
插图: 

三元搜索的递归实现: 

// C program to illustrate
// recursive approach to ternary search
 
#include <stdio.h>
 
// Function to perform Ternary Search
int ternarySearch(int l, int r, int key, int ar[])
{
    if (r >= l) {
 
        // Find the mid1 and mid2
        int mid1 = l + (r - l) / 3;
        int mid2 = r - (r - l) / 3;
 
        // Check if key is present at any mid
        if (ar[mid1] == key) {
            return mid1;
        }
        if (ar[mid2] == key) {
            return mid2;
        }
 
        // Since key is not present at mid,
        // check in which region it is present
        // then repeat the Search operation
        // in that region
 
        if (key < ar[mid1]) {
 
            // The key lies in between l and mid1
            return ternarySearch(l, mid1 - 1, key, ar);
        }
        else if (key > ar[mid2]) {
 
            // The key lies in between mid2 and r
            return ternarySearch(mid2 + 1, r, key, ar);
        }
        else {
 
            // The key lies in between mid1 and mid2
            return ternarySearch(mid1 + 1, mid2 - 1, key, ar);
        }
    }
 
    // Key not found
    return -1;
}
 
// Driver code
int main()
{
    int l, r, p, key;
 
    // Get the array
    // Sort the array if not sorted
    int ar[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
 
    // Starting index
    l = 0;
 
    // end element index
    r = 9;
 
    // Checking for 5
 
    // Key to be searched in the array
    key = 5;
 
    // Search the key using ternarySearch
    p = ternarySearch(l, r, key, ar);
 
    // Print the result
    printf("Index of %d is %d\n", key, p);
 
    // Checking for 50
 
    // Key to be searched in the array
    key = 50;
 
    // Search the key using ternarySearch
    p = ternarySearch(l, r, key, ar);
 
    // Print the result
    printf("Index of %d is %d", key, p);

输出
5 的指数为 4 
50 的指数为 -1

时间复杂度: O(2 * log 3 n)
辅助空间: O(log 3 n)

三元搜索的迭代方法:

// C program to illustrate
// iterative approach to ternary search
 
#include <stdio.h>
 
// Function to perform Ternary Search
int ternarySearch(int l, int r, int key, int ar[])
 
{
    while (r >= l) {
 
        // Find the mid1 and mid2
        int mid1 = l + (r - l) / 3;
        int mid2 = r - (r - l) / 3;
 
        // Check if key is present at any mid
        if (ar[mid1] == key) {
            return mid1;
        }
        if (ar[mid2] == key) {
            return mid2;
        }
 
        // Since key is not present at mid,
        // check in which region it is present
        // then repeat the Search operation
        // in that region
 
        if (key < ar[mid1]) {
 
            // The key lies in between l and mid1
            r = mid1 - 1;
        }
        else if (key > ar[mid2]) {
 
            // The key lies in between mid2 and r
            l = mid2 + 1;
        }
        else {
 
            // The key lies in between mid1 and mid2
            l = mid1 + 1;
            r = mid2 - 1;
        }
    }
 
    // Key not found
    return -1;
}
 
// Driver code
int main()
{
    int l, r, p, key;
 
    // Get the array
    // Sort the array if not sorted
    int ar[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
 
    // Starting index
    l = 0;
 
    // end element index
    r = 9;
 
    // Checking for 5
 
    // Key to be searched in the array
    key = 5;
 
    // Search the key using ternarySearch
    p = ternarySearch(l, r, key, ar);
 
    // Print the result
    printf("Index of %d is %d\n", key, p);
 
    // Checking for 50
 
    // Key to be searched in the array
    key = 50;
 
    // Search the key using ternarySearch
    p = ternarySearch(l, r, key, ar);
 
    // Print the result
    printf("Index of %d is %d", key, p);

输出
5 的指数为 4 
50 的指数为 -1

时间复杂度: O(2 * log 3 n),其中 n 是数组的大小。
辅助空间: O(1)

三元搜索的复杂度分析:
时间复杂度:
        最坏情况:O(log 3 N)
        平均情况: θ(log 3 N)
        最好的情况:Ω(1)
        辅助空间: O(1)

二元搜索与三元搜索:
        二分查找的时间复杂度低于三目查找,因为三目查找的比较次数比二分查找多得多。二分搜索用于查找单调函数的最大值/最小值,而三元搜索用于查找单峰函数的最大值/最小值。
        注意:我们也可以对单调函数使用三元搜索,但时间复杂度会比二分搜索稍高。
优点:
        三元搜索可以找到单峰函数的最大值/最小值,而二元搜索不适用。
        三元搜索的时间复杂度为O(2 * log 3 n),比线性搜索更高效,与二分搜索相当。
        非常适合优化问题。
缺点:
        三元搜索仅适用于有序列表或数组,不能用于无序或非线性数据集。
        与二元搜索相比,三元搜索需要更多时间来查找单调函数的最大值/最小值。

何时使用三元搜索:
        当您有一个大型有序数组或列表并且需要查找特定值的位置时。
        当您需要找到函数的最大值或最小值时。
        当您需要在双调序列中找到双调点时。
        当您必须计算二次表达式时
概括:
        三元搜索是一种分治算法,用于查找给定数组或列表中特定值的位置。
        它的工作原理是将数组分为三部分,并对适当的部分递归地执行搜索操作,直到找到所需的元素。 
        该算法的时间复杂度为 O(2 * log 3 n),比线性搜索更有效,但比二分搜索等其他搜索算法不太常用。 
        需要注意的是,要使三元搜索正常工作,要搜索的数组必须进行排序。

这篇关于c 语言 三元搜索 - 迭代与递归(Ternary Search)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/844995

相关文章

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

科研绘图系列:R语言扩展物种堆积图(Extended Stacked Barplot)

介绍 R语言的扩展物种堆积图是一种数据可视化工具,它不仅展示了物种的堆积结果,还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异,为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验

hdu 4517 floyd+记忆化搜索

题意: 有n(100)个景点,m(1000)条路,时间限制为t(300),起点s,终点e。 访问每个景点需要时间cost_i,每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问,并且当前点的访问价值应该严格大于前一个访问的点。 现在求,从起点出发,到达终点,在时间限制内,能得到的最大

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

hdu4277搜索

给你n个有长度的线段,问如果用上所有的线段来拼1个三角形,最多能拼出多少种不同的? import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

MiniGPT-3D, 首个高效的3D点云大语言模型,仅需一张RTX3090显卡,训练一天时间,已开源

项目主页:https://tangyuan96.github.io/minigpt_3d_project_page/ 代码:https://github.com/TangYuan96/MiniGPT-3D 论文:https://arxiv.org/pdf/2405.01413 MiniGPT-3D在多个任务上取得了SoTA,被ACM MM2024接收,只拥有47.8M的可训练参数,在一张RTX

如何确定 Go 语言中 HTTP 连接池的最佳参数?

确定 Go 语言中 HTTP 连接池的最佳参数可以通过以下几种方式: 一、分析应用场景和需求 并发请求量: 确定应用程序在特定时间段内可能同时发起的 HTTP 请求数量。如果并发请求量很高,需要设置较大的连接池参数以满足需求。例如,对于一个高并发的 Web 服务,可能同时有数百个请求在处理,此时需要较大的连接池大小。可以通过压力测试工具模拟高并发场景,观察系统在不同并发请求下的性能表现,从而