@@ -0,0 +1,1809 @@
+/*%0D%0Afrom http://www.geeksforgeeks.org/search-element-unsorted-array-using-minimum-number-comparisons/%0D%0ASearch an element in an unsorted array using minimum number of comparisons%0D%0AGiven an array of n distinct integers and an element x. %0D%0ASearch the element x in the array using minimum number of comparisons.%0D%0A Any sort of comparison will contribute 1 to the count of comparisons. %0D%0A For example, the condition used to terminate a loop, %0D%0A will also contribute 1 to the count of comparisons each time it gets executed. %0D%0A Expressions like while (n) %7BnC;%7D %0D%0A also contribute to the count of comparisons as value of n %0D%0A is being compared internally so as to decide whether or not to terminate the loop%0D%0A */%0D%0Apublic class SearchMiniCmp %7B%0D%0A%0D%0A%09public static void main(String%5B%5D args) %7B%0D%0A%09%09// TODO Auto-generated method stub%0D%0A%09int arr%5B%5D=%7B4, 6, 1, 5, 8%7D;%0D%0A%09int n = arr.length;%0D%0A%09int x = 1;%0D%0A%09String str = search(arr, n, x);%0D%0A%09System.out.println(str);%0D%0A%09%7D%0D%0A%09public static String search(int%5B%5D arr, int n, int x)%0D%0A%09%7B%0D%0A%09%09if (arr%5Bn-1%5D == x)%0D%0A%09%09%7B%0D%0A%09%09%09 return %22Found%22;%0D%0A%09%09%7D%0D%0A%09    int backup = arr%5Bn-1%5D;%0D%0A%09    arr%5Bn-1%5D = x;%0D%0A%09 %0D%0A%09    // no termination condition and thus%0D%0A%09    // no comparison%0D%0A%09    for (int i = 0; ;i++)%0D%0A%09    %7B%0D%0A%09        // this would be executed at-most n times%0D%0A%09        // and therefore at-most n comparisons%0D%0A%09        if (arr%5Bi%5D == x)%0D%0A%09        %7B%0D%0A%09            // replace arr%5Bn-1%5D with its actual element%0D%0A%09            // as in original 'arr%5B%5D'%0D%0A%09            arr%5Bn-1%5D = backup;%0D%0A%09 %0D%0A%09            // if 'x' is found before the '(n-1)th'%0D%0A%09            // index, then it is present in the array%0D%0A%09            // final comparison%0D%0A%09            if (i %3C n-1)%0D%0A%09                return %22Found%22;%0D%0A%09 %0D%0A%09            // else not present in the array%0D%0A%09            return %22Not Found%22;%0D%0A%09        %7D%0D%0A%09    %7D%0D%0A%09%7D%0D%0A%0D%0A%7D%0D%0A

Add files via upload