# 使用最少的比較次數搜索未排序數組中的元素 > 原文： [https://www.geeksforgeeks.org/search-element-unsorted-array-using-minimum-number-comparisons/](https://www.geeksforgeeks.org/search-element-unsorted-array-using-minimum-number-comparisons/) 給定 **n** 個不同整數的數組和一個元素 **x** 。 使用最少的比較次數在數組中搜索元素 **x** 。 任何種類的比較都會為比較計數貢獻 1。 例如，用于終止循環的條件也將在每次執行比較時為比較計數貢獻 1。 像 **while（n）{n–;}** 這樣的表達式也有助于比較計數，因為在內部對 **n** 的值進行了比較，從而決定是否終止循環。 例子： ``` Input : arr[] = {4, 6, 1, 5, 8}, x = 1 Output : Found Input : arr[] = {10, 3, 12, 7, 2, 11, 9}, x = 15 Output : Not Found ``` 在 Adobe 采訪中問 以下最簡單的搜索方法在最壞的情況下需要 **2n + 1** 比較。 ``` for (i = 0; i < n; i++) // Worst case n+1 if (arr[i] == x) // Worst case n return i; ``` **如何減少比較次數？** 的想法是將 x（要搜索的元素）復制到最后一個位置，以便保存 x 在 arr []中不存在時的最后一個比較。 **算法**： ``` search(arr, n, x) if arr[n-1] == x // 1 comparison return "true" backup = arr[n-1] arr[n-1] = x for i=0, i++ // no termination condition if arr[i] == x // execute at most n times // that is at-most n comparisons arr[n-1] = backup return (i < n-1) // 1 comparison ``` ## C/C++ ``` // C++ implementation to search an element in // the unsorted array using minimum number of // comparisons #include <bits/stdc++.h> using namespace std; // function to search an element in // minimum number of comparisons string search(int arr[], int n, int x) { ????// 1st comparison ????if (arr[n - 1] == x) ????????return "Found"; ????int backup = arr[n - 1]; ????arr[n - 1] = x; ????// no termination condition and thus ????// no comparison ????for (int i = 0;; i++) { ????????// this would be executed at-most n times ????????// and therefore at-most n comparisons ????????if (arr[i] == x) { ????????????// replace arr[n-1] with its actual element ????????????// as in original 'arr[]' ????????????arr[n - 1] = backup; ????????????// if 'x' is found before the '(n-1)th' ????????????// index, then it is present in the array ????????????// final comparison ????????????if (i < n - 1) ????????????????return "Found"; ????????????// else not present in the array ????????????return "Not Found"; ????????} ????} } // Driver program to test above int main() { ????int arr[] = { 4, 6, 1, 5, 8 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????int x = 1; ????cout << search(arr, n, x); ????return 0; } ``` ## Java ```java // Java implementation to search an element in // the unsorted array using minimum number of // comparisons import java.io.*; class GFG { ????// Function to search an element in ????// minimum number of comparisons ????static String search(int arr[], int n, int x) ????{ ????????// 1st comparison ????????if (arr[n - 1] == x) ????????????return "Found"; ????????int backup = arr[n - 1]; ????????arr[n - 1] = x; ????????// no termination condition and thus ????????// no comparison ????????for (int i = 0;; i++) { ????????????// this would be executed at-most n times ????????????// and therefore at-most n comparisons ????????????if (arr[i] == x) { ????????????????// replace arr[n-1] with its actual element ????????????????// as in original 'arr[]' ????????????????arr[n - 1] = backup; ????????????????// if 'x' is found before the '(n-1)th' ????????????????// index, then it is present in the array ????????????????// final comparison ????????????????if (i < n - 1) ????????????????????return "Found"; ????????????????// else not present in the array ????????????????return "Not Found"; ????????????} ????????} ????} ????// driver program ????public static void main(String[] args) ????{ ????????int arr[] = { 4, 6, 1, 5, 8 }; ????????int n = arr.length; ????????int x = 1; ????????System.out.println(search(arr, n, x)); ????} } // Contributed by Pramod Kumar ``` ## Python3 ```py # Python3 implementation to search an? # element in the unsorted array using? # minimum number of comparisons # function to search an element in # minimum number of comparisons def search(arr, n, x): ????# 1st comparison ????if (arr[n-1] == x) : ????????return "Found" ????backup = arr[n-1] ????arr[n-1] = x ????# no termination condition and? ????# thus no comparison ????i = 0 ????while(i < n) : ????????# this would be executed at-most n times ????????# and therefore at-most n comparisons ????????if (arr[i] == x) : ????????????# replace arr[n-1] with its actual? ????????????# element as in original 'arr[]' ????????????arr[n-1] = backup ????????????# if 'x' is found before the '(n-1)th' ????????????# index, then it is present in the? ????????????# array final comparison ????????????if (i < n-1): ????????????????return "Found" ????????????# else not present in the array ????????????return "Not Found" ????????i = i + 1 # Driver Code arr = [4, 6, 1, 5, 8] n = len(arr) x = 1 print (search(arr, n, x)) # This code is contributed by rishabh_jain ``` ## C# ```cs // C# implementation to search an? // element in the unsorted array? // using minimum number of comparisons using System; class GFG { ????// Function to search an element in ????// minimum number of comparisons ????static String search(int[] arr, int n, int x) ????{ ????????// 1st comparison ????????if (arr[n - 1] == x) ????????????return "Found"; ????????int backup = arr[n - 1]; ????????arr[n - 1] = x; ????????// no termination condition and thus ????????// no comparison ????????for (int i = 0;; i++) { ????????????// this would be executed at-most n times ????????????// and therefore at-most n comparisons ????????????if (arr[i] == x) { ????????????????// replace arr[n-1] with its actual element ????????????????// as in original 'arr[]' ????????????????arr[n - 1] = backup; ????????????????// if 'x' is found before the '(n-1)th' ????????????????// index, then it is present in the array ????????????????// final comparison ????????????????if (i < n - 1) ????????????????????return "Found"; ????????????????// else not present in the array ????????????????return "Not Found"; ????????????} ????????} ????} ????// driver program ????public static void Main() ????{ ????????int[] arr = { 4, 6, 1, 5, 8 }; ????????int n = arr.Length; ????????int x = 1; ????????Console.WriteLine(search(arr, n, x)); ????} } // This code is contributed by Sam007 ``` ## PHP ```php <?php // PHP implementation to? // search an element in // the unsorted array? // using minimum number of // comparisons // function to search an // element in minimum // number of comparisons function search($arr, $n, $x) { ????// 1st comparison ????if ($arr[$n - 1] == $x) ????????return "Found"; ????$backup = $arr[$n - 1]; ????$arr[$n - 1] = $x; ????// no termination? ????// condition and thus ????// no comparison ????for ($i = 0; ; $i++) ????{ ????????// this would be executed ????????// at-most n times and ????????// therefore at-most? ????????// n comparisons ????????if ($arr[$i] == $x)? ????????{ ????????????// replace arr[n-1]? ????????????// with its actual element ????????????// as in original 'arr[]' ????????????$arr[$n - 1] = $backup; ????????????// if 'x' is found before? ????????????// the '(n-1)th' index, ????????????// then it is present? ????????????// in the array ????????????// final comparison ????????????if ($i < $n - 1) ????????????????return "Found"; ????????????// else not present ????????????// in the array ????????????return "Not Found"; ????????} ????} } // Driver Code $arr = array( 4, 6, 1, 5, 8 ); $n = sizeof($arr); $x = 1; echo(search($arr, $n, $x)); // This code is contributed by Ajit. ?> ``` Output: ``` Found ``` 時間復雜度：`O(n)` 比較數：最多**（n + 2）**比較