Search an element in an unsorted array using minimum number of comparisons
Given an array of n distinct integers and an element x. Search the element x in the array using minimum number of comparisons. Any sort of comparison will contribute 1 to the count of comparisons. For example, the condition used to terminate a loop, will also contribute 1 to the count of comparisons each time it gets executed. Expressions like while (n) {n–;} also contribute to the count of comparisons as value of n is being compared internally so as to decide whether or not to terminate the loop.
Examples:
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
Asked in Adobe Interview
Below simple method to search requires 2n + 1 comparisons in worst case.
for (i = 0; i < n; i++) // Worst case n+1 if (arr[i] == x) // Worst case n return i;
How to reduce number of comparisons?
The idea is to copy x (element to be searched) to last location so that one last comparison when x is not present in arr[] is saved.
Algorithm:
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++ 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 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
# 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#
// 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 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. ?> |
Javascript
<script> // Javascript 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" ; let backup = arr[n - 1]; arr[n - 1] = x; // no termination condition and thus // no comparison for (let 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" ; } } } let arr = [ 4, 6, 1, 5, 8 ]; let n = arr.length; let x = 1; document.write(search(arr, n, x)); </script> |
Output:
Found
Time Complexity: O(n)
Auxiliary Space: O(1)
Number of Comparisons: Atmost (n+2) comparisons