线性插值 n-gram_搜索-线性/顺序，二进制和插值教程

傷城~ 2023-03-05 05:28 15阅读 0赞

线性插值 n-gram

## 数据结构搜索 **(**Data Structure Searching**)** ##

**Searching** is the process of finding an element in a given list. In this process, we check items that are available in the given list or not.

**搜索**是在给定列表中查找元素的过程。 在此过程中，我们将检查给定列表中是否可用的项目。

## 搜索类型 **(**Type of searching**)** ##

1.  **Internal Search**: In this search, **searching** is performed on main or primary memory.
    
    **内部搜索** ：在此搜索中，对主存储器或主存储器执行**搜索** 。
2.  **External Search**: In this search, **searching** is performed in secondary memory.
    
    **外部搜索** ：在此搜索中， **搜索**在辅助存储器中进行。

**Complexity Analysis**

**复杂度分析**

Complexity analysis is used to determine, the algorithm will take the number of resources (such as time and space) necessary to execute it.

复杂度分析用于确定该算法将占用执行它所需的资源数量(例如时间和空间)。

There are two types of complexities: **1) Time Complexity** and **2) Space Complexity**.

复杂度有两种类型： **1)时间复杂度**和**2)空间复杂度** 。

## 搜索技术 **(**Searching Techniques**)** ##

There are three types of searching techniques,

共有三种搜索技术，

1.  Linear or sequential search
    
    线性或顺序搜索
2.  Binary search
    
    二元搜寻
3.  Interpolation search
    
    插补搜索

### A)线性/顺序搜索 **(**A) Linear/ Sequential Search**)** ###

**Linear/Sequential searching** is a searching technique to find an item from a list until the particular item not found or list not reached at the end. We start the searching from *0th* index to *Nth\-1* index in a sequential manner, if a particular item found, returns the position of that item otherwise return failure status or *-1*.

**线性/顺序搜索**是一种搜索技术，用于从列表中查找项目，直到找不到特定项目或最后没有到达列表为止。 我们以从*第 0 个*索引到*第 N 个 \-1*索引的顺序开始搜索，如果找到特定项目，则返回该项目的位置，否则返回失败状态或*-1* 。

![Linear Searching - Data Structure Tutorial][]

**Algorithm:**

**算法：**

LINEAR_SEARCH (LIST, N, ITEM, LOC, POS)
    In this algorithm, LIST is a linear array with N elements, 
    and ITEM is a given item to be searched. This algorithm finds 
    the location LOC of ITEM into POS in LIST, or sets POS := 0, 
    if search is unsuccessfull.
    1.	Set POS  :=  0;
    2.	Set LOC  :=  1;
    3.	Repeat STEPS a and b while LOC <= N
        a.	If ( LIST[LOC] = ITEM) then 
            i.	SET POS := LOC;  [get position of item]
            ii.	return;
        b.	Otherwise
            i.	SET LOC := LOC + 1 ; [increment counter]
    4.	[END OF LOOP]
    5.	return

**Complexity of Linear search:**

**线性搜索的复杂度：**

The complexity of the search algorithm is based on the number of comparisons *C*, between *ITEM* and *LIST \[LOC\]*. We seek *C (n)* for the worst and average case, where *n* is the size of the list.

搜索算法的复杂性基于*ITEM*和*LIST \[LOC\]*之间的比较次数*C。* 我们寻找最差和平均的情况下的*C(n)* ，其中*n*是列表的大小。

**Worst Case**: The worst case occurs when *ITEM* is present at the last location of the list, or it is not there at al. In either situation, we have, *C (n) = n*

**最坏的情况** ：最坏的情况是： *ITEM*位于列表的最后一个位置，或者根本不存在。 无论哪种情况，我们都有*C(n)= n*

Now, *C (n) = n* is the worst-case complexity of **linear or sequential search algorithm**.

现在， *C(n)= n*是**线性或顺序搜索算法**的最坏情况复杂度。

**Average case**: In this case, we assume that *ITEM* is there in the list, and it can be present at any position in the list. Accordingly, the number of comparisons can be any of the numbers *1, 2, 3, 4, ..., n*. and each number occurs with probability *p = 1/n*. Then,  
*C (n) = n/2*

**一般情况** ：在这种情况下，我们假定*ITEM*在列表中，并且它可以出现在列表中的任何位置。 因此，比较次数可以是*1、2、3、4，...，n中的任何一个* 。 每个数字的出现概率为*p = 1 / n* 。 然后，  
*C(n)= n / 2*

#### 线性/顺序搜索的实现 **(**Implementation of Linear/ Sequential Search**)** ####

*  [Using C][]
    
    [使用C][Using C]
 *  [Using C++][Using C 1]
    
    [使用C ++][Using C 1]

#include <stdio.h>
    #define SIZE 5
    
    /*Function to search item from list*/
    int LinearSearch(int ele[], int item)
    {
        int POS = -1;
        int LOC = 0;
    
        for (LOC = 0; LOC < SIZE; LOC++) {
            if (ele[LOC] == item) {
                POS = LOC;
                break;
            }
        }
    
        return POS;
    }
    
    int main()
    {
        int ele[SIZE];
        int i = 0;
        int item;
        int pos;
    
        printf("\nEnter Items : \n");
    
        for (i = 0; i < SIZE; i++) {
            printf("Enter ELE[%d] : ", i + 1);
            scanf("%d", &ele[i]);
        }
    
        printf("\n\nEnter Item To Be Searched : ");
        scanf("%d", &item);
    
        pos = LinearSearch(ele, item);
    
        if (pos >= 0) {
            printf("\nItem Found At Position : %d\n", pos + 1);
        }
        else {
            printf("\nItem Not Found In The List\n");
        }
    
        return 0;
    }

First run:
    
        Enter Items : 
        Enter ELE[1] : 20
        Enter ELE[2] : 10
        Enter ELE[3] : 30
        Enter ELE[4] : 40
        Enter ELE[5] : 50
    
    
        Enter Item To Be Searched : 30
    
        Item Found At Position : 3
    
        Second run:
    
        Enter Items : 
        Enter ELE[1] : 20
        Enter ELE[2] : 10
        Enter ELE[3] : 30
        Enter ELE[4] : 40
        Enter ELE[5] : 50
    
    
        Enter Item To Be Searched : 24
    
        Item Not Found In The List

#include <iostream>
    
    using namespace std;
    #define SIZE 5
    
    class Search {
    private:
        int ele[SIZE];
    
    public:
        void Input();
        int LinearSearch(int item);
    };
    
    //Input Element into the list
    void Search::Input()
    {
        int i = 0;
    
        cout << "\nEnter Items : \n";
    
        for (i = 0; i < SIZE; i++) {
            cout << "Enter ELE[" << i + 1 << "] : ";
            cin >> ele[i];
        }
    }
    
    //Function to search item from list
    int Search::LinearSearch(int item)
    {
        int POS = -1;
        int LOC = 0;
    
        for (LOC = 0; LOC < SIZE; LOC++) {
            if (ele[LOC] == item) {
                POS = LOC;
                break;
            }
        }
    
        return POS;
    }
    
    int main()
    {
        int i = 0;
        int item;
        int pos;
    
        Search s = Search();
    
        s.Input();
    
        cout << "\n\nEnter Item To Be Searched : ";
        cin >> item;
    
        pos = s.LinearSearch(item);
    
        if (pos >= 0) {
            cout << "\nItem Found At Position : " << pos + 1 << endl;
        }
        else {
            cout << "\nItem Not Found In The List\n";
        }
    
        return 0;
    }

### B)二进制搜索 **(**B) Binary Search**)** ###

It is a special type of search work on a sorted list only. During each stage of our procedure, our search for *ITEM* is reduced to a restricted segment of elements in *LIST* array. The segment starts from index *LOW* and spans to *HIGH*.

它是仅在排序列表上的一种特殊类型的搜索工作。 在过程的每个阶段，对*ITEM*的搜索都会减少为*LIST*数组中元素的受限部分。 该段从索引*LOW*开始，跨度为*HIGH* 。

LIST [LOW], LIST [LOW+1], LIST [LOW+2], LIST [LOW+ 3]….. LIST[HIGH]

The *ITEM* to be searched is compared with the middle element *LIST\[MID\]* of segment, where *MID* obtained as,

将要搜索的*ITEM*与分段的中间元素*LIST \[MID\]*进行比较，其中获得的*MID*为

MID = ( LOW + HIGH )/2

We assume that the *LIST* is sorted in ascending order. There may be three results of this comparison,

我们假设*LIST*是按升序排序的。 此比较可能有三个结果，

1.  If *ITEM = LIST\[MID\]*, the search is successful. The location of the *ITEM* is *LOC := MID*.
    
    如果*ITEM = LIST \[MID\]* ，则搜索成功。 *ITEM*的位置是*LOC：= MID* 。
2.  If *ITEM < LIST\[MID\]*, the *ITEM* can appear only in the first half of the list. So, the segment is restricted by modifying *HIGH = MID - 1*.
    
    如果*ITEM <LIST \[MID\]* ，则*ITEM*只能出现在列表的前半部分。 因此，通过修改*HIGH = MID-1*来限制该分段。
3.  If *ITEM > LIST\[MID\]*, the *ITEM* can appear only in the second half of the list. So, the segment is restricted by modifying *LOW = MID + 1*.
    
    如果*ITEM> LIST \[MID\]* ，则*ITEM*只能出现在列表的后半部分。 因此，通过修改*LOW = MID + 1*来限制该段。

Initially, *LOW* is the start index of the array, and *HIGH* is the last index of the array. The comparison goes on. With each comparison, low and high approaches near to each other. The loop will continue till *LOW < HIGH*.

最初， *LOW*是数组的开始索引，而*HIGH*是数组的最后索引。 比较继续进行。 每次比较时，高低彼此接近。 循环将持续到*LOW <HIGH*为止。

![Binary Searching - Data Structure Tutorial][]

**Algorithm**

**算法**

Let the item to be searched is: 15
    Step1: Initially
        1.	List[low]  = list[0] = 12
        2.	List[high] = list[9] = 99
        3.	Mid= (low + high)/2 = (0+9)/2 = 4
        4.	List[mid]=  list[4] = 35
    Step2: Since item (15) < list [mid] (35); high = mid -1 = 3
        1.	List[low]  = list[0] = 12
        2.	List[high] = list[3] = 28
        3.	Mid =(low + high)/2 = (0+3)/2 = 1
        4.	List [mid] = list [1] = 15.
    Step3: Since item (15) = list [mid] (15); 
    It is success, the location 1 is returned.

BINARY SEARCH (LIST, N, ITEM, LOC, LOW, MID, HIGH)
    Here LIST is a sorted array with size N, ITEM is the given information. 
    The variable LOW, HIGH and MID denote, respectively,
    the beginning, end and the middle of segment of LIST. 
    The algorithm is used to find the location LOC of ITEM in LIST array. 
    If ITEM not there LOC is NULL.
    
    1.	Set LOW := 1; LOW := N;
    2.	Repeat step a  to d while LOW <= HIGH and ITEM != LIST(MID)
        a.	Set MID := (LOW + HIGH)/2
        b.	If ITEM = LIST(MID), then
            i.	Set LOC := MID
            ii.	Return
        c.	If ITEM < LIST(MID) then
            i.	Set HIGH := MID - 1;
        d.	Otherwise
            i.	Set LOW := MID + 1;
    3.	SET  LOC := NULL
    4.	return

**Complexity of Binary search**

**二元搜索的复杂性**

The complexity measured by the number *f(n)* of comparisons to locate *ITEM* in *LIST* where *LIST* contains n elements. Each comparison reduces the segment size in half.

用比较数*f(n)*衡量的复杂性，以在*LIST*包含n个元素的*LIST*中定位*ITEM* 。 每次比较将段大小减小一半。

Hence, we require at most *f(n)* comparisons to locate *ITEM*, where, *2c >= n*

因此，我们最多需要*f(n)个*比较才能找到*ITEM* ，其中*2 c > = n*

Approximately, the time complexity is equal to *log2n*. It is much less than the time complexity of a linear search.

近似地，时间复杂度等于*log 2 n* 。 它远小于线性搜索的时间复杂度。

#### 二进制搜索的实现 **(**Implementation of Binary Search**)** ####

*  [Using C][Using C 2]
    
    [使用C][Using C 2]
 *  [Using C++][Using C 3]
    
    [使用C ++][Using C 3]

#include <stdio.h>
    #define SIZE 5
    
    /*To search item from sorted list*/
    int BinarySearch(int ele[], int item)
    {
        int POS = -1;
        int LOW = 0;
        int HIGH = SIZE;
        int MID = 0;
    
        while (LOW <= HIGH) {
            MID = (LOW + HIGH) / 2;
    
            if (ele[MID] == item) {
                POS = MID;
                break;
            }
            else if (item > ele[MID]) {
                LOW = MID + 1;
            }
            else {
                HIGH = MID - 1;
            }
        }
    
        return POS;
    }
    
    int main()
    {
        int ele[SIZE];
        int i = 0;
        int item;
        int pos;
    
        printf("\nEnter Items : \n");
    
        for (i = 0; i < SIZE; i++) {
            printf("Enter ELE[%d] : ", i + 1);
            scanf("%d", &ele[i]);
        }
    
        printf("\n\nEnter Item To Be Searched : ");
        scanf("%d", &item);
    
        pos = BinarySearch(ele, item);
    
        if (pos >= 0) {
            printf("\nItem Found At Position : %d\n", pos + 1);
        }
        else {
            printf("\nItem Not Found In The List\n");
        }
    
        return 0;
    }

First run:
    
        Enter Items : 
        Enter ELE[1] : 10
        Enter ELE[2] : 20
        Enter ELE[3] : 30
        Enter ELE[4] : 40
        Enter ELE[5] : 50
    
    
        Enter Item To Be Searched : 30
    
        Item Found At Position : 3
    
        Second run:
    
        Enter Items : 
        Enter ELE[1] : 10
        Enter ELE[2] : 20
        Enter ELE[3] : 30
        Enter ELE[4] : 40
        Enter ELE[5] : 50
    
    
        Enter Item To Be Searched : 24
    
        Item Not Found In The List

#include <iostream>
    
    using namespace std;
    #define SIZE 5
    
    class Search {
    private:
        int ele[SIZE];
    
    public:
        void Input();
        int BinarySearch(int item);
    };
    
    //Input Element into the list
    void Search::Input()
    {
        int i = 0;
    
        cout << "\nEnter Items : \n";
    
        for (i = 0; i < SIZE; i++) {
            cout << "Enter ELE[" << i + 1 << "] : ";
            cin >> ele[i];
        }
    }
    
    //To search item from sorted list
    int Search::BinarySearch(int item)
    {
        int POS = -1;
        int LOW = 0;
        int HIGH = SIZE;
        int MID = 0;
    
        while (LOW <= HIGH) {
            MID = (LOW + HIGH) / 2;
    
            if (ele[MID] == item) {
                POS = MID;
                break;
            }
            else if (item > ele[MID]) {
                LOW = MID + 1;
            }
            else {
                HIGH = MID - 1;
            }
        }
    
        return POS;
    }
    
    int main()
    {
        int i = 0;
        int item;
        int pos;
    
        Search s = Search();
    
        s.Input();
    
        cout << "\n\nEnter Item To Be Searched : ";
        cin >> item;
    
        pos = s.BinarySearch(item);
    
        if (pos >= 0) {
            cout << "\nItem Found At Position : " << pos + 1 << endl;
        }
        else {
            cout << "\nItem Not Found In The List\n";
        }
    
        return 0;
    }

## 线性搜索和二进制搜索之间的区别 **(**Difference between Linear Search and Binary Search**)** ##

<table> 
 <tbody> 
  <tr> 
   <th>Linear Search</th> 
   <th>Binary Search</th> 
  </tr> 
  <tr> 
   <td>Sorted list is not required.</td> 
   <td>Sorted list is required.</td> 
  </tr> 
  <tr> 
   <td>It can be used in linked list implementation.</td> 
   <td>It cannot be used in liked list implementation.</td> 
  </tr> 
  <tr> 
   <td>It is suitable for a list changing very frequently.</td> 
   <td>It is only suitable for static lists, because any change requires resorting of the list.</td> 
  </tr> 
  <tr> 
   <td>The average number of comparison is very high.</td> 
   <td>The average number of comparison is relatively slow.</td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <th> 线性搜寻 </th> 
   <th> 二进制搜索 </th> 
  </tr> 
  <tr> 
   <td> 不需要排序列表。 </td> 
   <td> 排序列表是必需的。 </td> 
  </tr> 
  <tr> 
   <td> 它可以在链表实现中使用。 </td> 
   <td> 不能在顶列表实现中使用。 </td> 
  </tr> 
  <tr> 
   <td> 它适用于经常更改的列表。 </td> 
   <td> 它仅适用于静态列表，因为任何更改都需要使用列表。 </td> 
  </tr> 
  <tr> 
   <td> 平均比较数很高。 </td> 
   <td> 比较的平均次数相对较慢。 </td> 
  </tr> 
 </tbody> 
</table>

### C)插补搜索 **(**C) Interpolation Search**)** ###

This technique is used if the items to be searched are uniformly distributed between the first and the last location. This technique is a simple modification in the binary search when *MID* is calculated.

如果要搜索的项目在第一个位置和最后一个位置之间均匀分布，则使用此技术。 计算*MID*时，此技术是对二进制搜索的简单修改。

Mid = low + (high – low) * ((item – LIST[low])  / (LIST[high] – LIST[low]));

**Advantages**

**优点**

1.  If the items are uniformly distributed, the average case time complexity is log2(log2(n)).
    
    如果项目是均匀分布的，则平均案例时间复杂度为log 2 (log 2 (n))。
2.  It is considered an improvement in binary search.
    
    它被认为是对二进制搜索的一种改进。

**Disadvantages**

**缺点**

1.  The calculation of mid is complicated. It increases the execution time.
    
    中值的计算很复杂。 它增加了执行时间。
2.  If the items are not uniformly distributed, the interpolation search will have very poor behavior.
    
    如果项目分布不均匀，则插值搜索的行为将非常差。

> 翻译自: [https://www.includehelp.com/data-structure-tutorial/linear-sequential-binary-interpolation- searching-in-data-structure-tutorial.aspx][https_www.includehelp.com_data-structure-tutorial_linear-sequential-binary-interpolation- searching-in-data-structure-tutorial.aspx]

线性插值 n-gram

[Linear Searching - Data Structure Tutorial]: https://www.includehelp.com/screen-shots/linear-searching.jpg
[Using C]: https://www.includehelp.com/data-structure-tutorial/linear-sequential-binary-interpolation-%20searching-in-data-structure-tutorial.aspx#view3
[Using C 1]: https://www.includehelp.com/data-structure-tutorial/linear-sequential-binary-interpolation-%20searching-in-data-structure-tutorial.aspx#view4
[Binary Searching - Data Structure Tutorial]: /images/20230208/c6dc8b08cdc4450eb188305745ae80f2.png
[Using C 2]: https://www.includehelp.com/data-structure-tutorial/linear-sequential-binary-interpolation-%20searching-in-data-structure-tutorial.aspx#view1
[Using C 3]: https://www.includehelp.com/data-structure-tutorial/linear-sequential-binary-interpolation-%20searching-in-data-structure-tutorial.aspx#view2
[https_www.includehelp.com_data-structure-tutorial_linear-sequential-binary-interpolation- searching-in-data-structure-tutorial.aspx]: https://www.includehelp.com/data-structure-tutorial/linear-sequential-binary-interpolation-%20searching-in-data-structure-tutorial.aspx