순차 검색(순서 테이블) 애니메이션 데모

顾名思义，哨兵线性搜索，顺序查找有序表是线性搜索的一种，与传统线性搜索相比，比较次数减少了。在传统的线性搜索中，仅进行N次比较，而在哨兵线性搜索，顺序查找有序表中，哨兵值用于避免任何越界比较，但没有专门针对正在搜索的元素的索引进行额外的比较。

在这种搜索中，将数组的最后一个元素替换为要搜索的元素，然后对数组进行线性搜索，而不检查当前索引是否在数组的索引范围内，因为要搜索的元素即使它不存在于原始数组中，也肯定会在数组中找到，因为最后一个元素被替换为它。因此，要检查的索引永远不会超出数组的范围。最坏情况下的比较次数将为(N+2)。

哨兵线性搜索，顺序查找有序表是标准线性搜索算法的变体，用于在数组或列表中查找目标值。该算法背后的基本思想是在数组末尾添加一个标记值，该值等于我们正在查找的目标值。这有助于避免在循环的每次迭代期间检查数组边界条件，因为哨兵值充当循环的停止器。

尽管在最坏情况下时间复杂度这两种算法都是 O(n)。只是哨兵线性搜索，顺序查找有序表比线性搜索少了比较次数

使用哨兵线性搜索，顺序查找有序表：

在搜索数组中的元素时，哨兵线性搜索，顺序查找有序表是线性搜索算法的变体，它使用哨兵值来优化搜索过程。

哨兵线性搜索，顺序查找有序表的基本思想是在数组末尾添加一个与搜索键匹配的额外元素（即哨兵值）。通过这样做，我们可以避免在循环中对数组末尾进行条件检查，并在找到哨兵元素后尽早终止搜索。这消除了对数组末尾进行单独检查的需要，从而使算法的平均情况性能略有提高。

Sentinel线性搜索算法的步骤如下：

将搜索索引变量 i 初始化为 0。
将数组的最后一个元素设置为搜索键。
当搜索键不等于数组的当前元素（即 arr[i]）时，增加搜索索引 i。
如果 i 小于数组大小或 arr[i] 等于搜索键，则返回 i 的值（即搜索键在数组中的索引）。
否则，搜索键不存在于数组中，因此返回 -1（或任何其他适当的值来指示未找到该键）。

Sentinel 线性搜索算法的主要好处是它不需要单独检查数组末尾，这可以提高算法的平均情况性能。然而，它并没有改善最坏情况下的性能，仍然是 O(n)（其中 n 是数组的大小），因为我们可能需要扫描整个数组才能找到哨兵值。
例子：

输入： arr[] = {10, 20, 180, 30, 60, 50, 110, 100, 70}, x = 180 输出
： 180 出现在索引 2
输入： arr[] = {10, 20, 180, 30, 60, 50, 110, 100, 70}, x = 90
输出： 未找到

下面是上述方法的实现：

C++
Java
Python3
C＃
JavaScript

C++

              
                
                    // C++ implementation of the approach
#include <iostream>
using namespace std;
 
// Function to search x in the given array
void sentinelSearch(int arr[], int n, int key)
                        
{
 
    // Last element of the array
    int
                          last = arr[n - 1];
 
    // Element to be searched is
    // placed at the last index
    arr[n - 1] = key;
    int
                          i = 0;
 
    while (arr[i] != key)
        i++;
 
    // Put the last element back
    arr[n - 1] = last;
 
    if
                          ((i < n - 1) || (arr[n - 1] == key))
        cout << key << " is present at index " << i;
    else
        cout << "Element Not found";
}
 
// Driver code
int main()
{
    int
                          arr[] = { 10, 20, 180, 30, 60, 50, 110, 100, 70 };
    int
                          n = sizeof(arr) / sizeof(arr[0]);
    int
                          key = 180;
 
    sentinelSearch(arr, n, key);
 
    return 0;
}
// This code is contributed by Mandeep Dalavi

                  

              
            

Java

              
                
                    // Java implementation of the approach
class GFG {
 
    // Function to search x in the given array
    static
                          void sentinelSearch(int arr[], int n, int
                          key)
    {
 
        // Last element of the array
        int last = arr[n - 1];
 
        // Element to be searched is
        // placed at the last index
        arr[n - 1] = key;
                        
        int i = 0;
 
        while (arr[i] != key)
            i++;
 
        // Put the last element back
        arr[n - 1] = last;
 
        if ((i < n - 1) || (arr[n - 1] == key))
            System.out.println(key + " is present at index "
                               + i);
        else
            System.out.println("Element Not found");
    }
 
    // Driver code
    public
                          static void main(String[] args)
    {
        int arr[]
            = { 10, 20, 180, 30, 60, 50, 110, 100, 70 };
        int n = arr.length;
        int key = 180;
 
        sentinelSearch(arr, n, key);
    }
}
 
// This code is contributed by Ankit Rai, Mandeep Dalavi

                  

              
            

Python3

              
                    # Python3 implementation of the approach
# Function to search key in the given array
 
def sentinelSearch(arr, n, key):
 
    # Last element of the array
    last = arr[n - 1]
 
    # Element to be searched is
    # placed at the last index
    arr[n - 1] = key
    i = 0
 
    while
                          (arr[i] != key):
        i += 1
 
    # Put the last element back
    arr[n - 1] = last
 
    if
                          ((i < n - 1) or (arr[n - 1] == key)):
        print(key, "is present at index", i)
    else:
        print("Element Not found")
 
# Driver code
arr = [10, 20, 180, 30, 60, 50, 110, 100, 70]
n = len(arr)
                        
key = 180
 
sentinelSearch(arr, n, key)
                        
# This code is contributed by divyamohan123, Mandeep Dalavi

C＃

              
                
                    // C# implementation of the approach
using System;
 
class GFG {
 
    // Function to search x in the given array
    static
                          void sentinelSearch(int[] arr, int n, int
                          key)
    {
 
        // Last element of the array
        int last = arr[n - 1];
 
        // Element to be searched is
        // placed at the last index
        arr[n - 1] = key;
        int i = 0;
 
        while (arr[i] != key)
            i++;
 
        // Put the last element back
        arr[n - 1] = last;
 
        if ((i < n - 1) || (arr[n - 1] == key))
                        
            Console.WriteLine(key + " is present"
                              + " at index " + i);
        else
            Console.WriteLine("Element Not found");
    }
 
    // Driver code
    public
                          static void Main()
    {
        int[] arr
            = { 10, 20, 180, 30, 60, 50, 110, 100, 70 };
        int n = arr.Length;
        int key = 180;
 
        sentinelSearch(arr, n, key);
    }
}
 
// This code is contributed by Mohit kumar, Mandeep Dalavi

                  

              
            

JavaScript

              
                    <script>
// javascript implementation of the approach    
                        
// Function to search x in the given array
    function sentinelSearch(arr , n , key) {
                        
        // Last element of the array
        var last = arr[n - 1];
 
        // Element to be searched is
        // placed at the last index
        arr[n - 1] = key;
        var i = 0;
 
        while (arr[i] != key)
            i++;
 
        // Put the last element back
        arr[n - 1] = last;
 
        if ((i < n - 1) || (arr[n - 1] == key))
                        
            document.write(key + " is present at index " + i);
        else
            document.write("Element Not found");
    }
 
    // Driver code
     
        var arr = [ 10, 20, 180, 30, 60, 50, 110, 100, 70 ];
        var n = arr.length;
        var key = 180;
 
        sentinelSearch(arr, n, key);
 
// This code is contributed by todaysgaurav 
</script>

输出

180 出现在索引 2 处

时间复杂度： O(N)
辅助空间： O(1)

方法二：

以下是哨兵线性搜索，顺序查找有序表算法涉及的步骤：

将数组的最后一个元素设置为目标值。这称为哨兵值。
将索引变量“i”设置为数组的第一个元素。
使用循环迭代数组，将每个元素与目标值进行比较。
如果当前元素等于目标值，则返回当前元素的索引。
每次循环迭代后将索引变量“i”增加 1。
如果循环完成但未找到目标值，则返回 -1 以指示该值不存在于数组中。

哨兵线性搜索，顺序查找有序表算法对于具有大量元素的数组非常有用，其中目标值可能位于数组的末尾。通过在数组末尾添加哨兵值，我们可以消除在循环的每次迭代期间检查数组边界条件的需要，从而减少算法的整体运行时间。

C++
Java
Python3
C＃
JavaScript

C++

              
                
                    #include <iostream>
#include <vector>
                        
 
int sentinelLinearSearch(std::vector<int> array, int key) {
    int
                          last = array[array.size() - 1];
    array[array.size() - 1] = key;
    int
                          i = 0;
    while (array[i] != key) {
        i++;
    }
    array[array.size() - 1] = last;
    if
                          (i < array.size() - 1 || last == key) {
        return i;
    } else {
        return -1;
    }
}
 
int main() {
    std::vector<int> array = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int
                          key = 5;
    int
                          index = sentinelLinearSearch(array, key);
    if
                          (index == -1) {
        std::cout << key << " is not found in the array." << std::endl;
    } else {
        std::cout << key << " is found at index " << index << " in the array."
                          << std::endl;
    }
    return 0;
}

                  

              
            

Java

              
                
                    import java.util.Arrays;
 
public class SentinelLinearSearch {
    public
                          static int sentinelLinearSearch(int[] array, int key) {
        int last = array[array.length - 1];
        array[array.length - 1] = key;
        int i = 0;
        while (array[i] != key) {
            i++;
        }
        array[array.length - 1] = last;
        if (i < array.length - 1 || last == key) {
            return i;
        } else {
            return -1;
        }
    }
    public
                          static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int key = 5;
        int index = sentinelLinearSearch(array, key);
        if (index == -1) {
            System.out.println(key + " is not found in the array: " + Arrays.toString(array));
        } else {
            System.out.println(key + " is found at index " + index + " in the array: " + Arrays.toString(array));
        }
    }
}

                  

              
            

Python3

              
                
                    def sentinelLinearSearch(array, key):
    last = array[len(array) - 1]
    array[len(array) - 1] = key
    i = 0
    while
                          array[i] != key:
        i += 1
    array[len(array) - 1] = last
    if
                          i < len(array) - 1
                          or last == key:
        return i
    else:
        return -1
                        
 
array = [1, 2, 3, 4, 5, 6, 7, 8, 9]
key = 5
index = sentinelLinearSearch(array, key)
if index ==
                          -1:
    print(f"{key} is not found in the array: {array}")
                        
else:
    print(f"{key} is found at index {index} in the array: {array}")

                  

              
            

C＃

              
                
                    using System;
using System.Collections.Generic;
 
class MainClass {
    static
                          int SentinelLinearSearch(List<int> array, int key) {
        int last = array[array.Count - 1];
        array[array.Count - 1] = key;
        int i = 0;
        while (array[i] != key) {
            i++;
        }
        array[array.Count - 1] = last;
        if (i < array.Count - 1 || last == key) {
            return i;
        } else {
            return -1;
        }
    }
 
    static
                          void Main() {
        List<int> array = new List<int> {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int key = 5;
        int index = SentinelLinearSearch(array, key);
        if (index == -1) {
            Console.WriteLine(key + " is not found in the array.");
        } else {
            Console.WriteLine(key + " is found at index " + index + " in the array.");
        }
    }
}
//this code is contributed by snehalsalokhe

                  

              
            

JavaScript

              
                
                    // JavaScript
 
// Function to search key in given array
function sentinelLinearSearch(array, key)
{
 
    // Store the last element of the array
    let last = array[array.length - 1];
     
    // Replace the last element of the array with the key value
    array[array.length - 1] = key;
     
    // Initialize the index
    let i = 0;
     
    // Check if the array element is equal to the key
    while
                          (array[i] !== key) {
        i++;
    }
     
    // Replace the last element of the array with the stored last element
                        
    array[array.length - 1] = last;
     
    // Check if the key is found in the array
    if
                          (i < array.length - 1 || last == key) {
        return i;
    } else {
        return -1;
    }
}
 
// Array of numbers
let array = [1, 2, 3, 4, 5, 6, 7, 8, 9];
 
// Key to be searched
                        
let key = 5;
 
// Find index of the key in the array
let index = sentinelLinearSearch(array, key);
 
// Print result
if (index == -1) {
    console.log(`${key} is not found in the array: ${array}`)
} else {
    console.log(`${key} is found at index ${index} in the array: ${array}`)
}

                  

              
            

输出

5 在数组中的索引 4 处找到：[1, 2, 3, 4, 5, 6, 7, 8, 9]

时间复杂度：

Sentinel 线性搜索算法的时间复杂度在最坏情况下为 O(n)。

在最好的情况下，当第一次迭代找到密钥时，时间复杂度将为 O(1)。

然而，平均时间复杂度仍然是O(n)，因为平均来说，key会在