Search an element in an unsorted array using minimum number of comparisons

Given an array and an element, search the element x in the array using minimum number of comparisons.

/**This is generic algorithm which takes 2n+1

 * comparisons(worst case) to search element. */

private static int searchElementUsingGenericAlgo(int[] array, intvalue) {

     int idx = -1;

     int length = array.length;

     for (inti = 0;i<length; i++) { /* n+1 comparisons. */

           if(value == array[i]) { /* n comparisons. */

                idx = i;

                break;

           }

     }

     return idx;

}

This algorithm is developed to return the element index in 2n+1 comparison in the worst case.

Approach:

To avoid the comparison that is taking place in the loop.

Algorithm:

1. Check that the last element in the array is equal to searched element.

   a. YES, element index is found, return the index.

   b. NO, Take back up of last element and put the searched element on last index of array.

2. Search for element with Infinite loop (without termination condition) and break when the element is found

   a. If element is found on last index, this is the element put by us to terminate the search and this signals that element not found in the array.

   b. If element found other than last index, set the backup to last index and return the index.

public class MinComparison {

     /**This algorithm is developed to return the

      * element index in n+1 comparison in the worst case.

      * Approach: To avoid the comparison that is taking place in the loop.

      * Steps:

      * 1. Check that the last element in the array is equal to searched element.

      *     a. YES, element index is found, return the index.

      *    b. NO, Take back up of last element and put the searched element on last index of array.

      * 2. Search for element with Infinite loop(without termination condition) and break when the element is found

      *    a. If element is found on last index, this is the element put by us to terminate

      *       the search and this signals that element not found in the array.

      *    b. If element found other than last index, set the backup to last index and return the index.

      **/

     private static int searchElement(int[] array, intvalue) {

           int idx = -1;

           int length = array.length;

           int backup = array[length-1];

           if(backup==value) {

                return (length-1);

           }

           array[length-1] = value;

           for (inti = 0;; i++) {

                if(value == array[i]) { /* n comparisons. */

                     idx = i;

                     break;

                }

           }

           if(idx==length-1) { /* 1 comparison. */

                idx = -1;

           }

           return idx;

     }

    

     public static void main(String[] args) {

           int value = 1;

           int [] array = {4, 6, 1, 5, 8};

           int index = searchElement(array, value);

           System.out.println("Element index in array "+index);

     }

}

This algorithm is developed to return the element index in n+1 comparison in the worst case.

Check if a singly linked list is palindrome or not

Given a singly linked list of integers, check whether the linked list is palindrome or not using O(1) space complexity.

In this approach, we need to modify the existing linked list.

1) Get the middle of the linked list.

2) Reverse the second half of the linked list.

3) Check if the first half and second half are identical.

4) Construct the original linked list by reversing the second half again and attaching it back to the first half.

package com.geeks;

/**

 * Class to check whether integer list is palindrome or not.

 * @author rajesh.dixit

 */

public class PalidromeList {

     /** Node definition. */

     private static class Node {

           int data; Node next;

           Node(int data) {

                this.data = data;

                this.next = null;

           }

     }

     /**

      * @param head

      * @return String palindrome or not.

      */

     private static String checkListIsPalindrome(Node head) {

           boolean result = false;

           if(head==null) {

                System.out.println("List is null");

           } else if(head.next==null) {

                result = true;

           } else if(head.next.next==null) {

                result = (head.data == head.next.data);

           } else {

                /** Reverse the second half of linked list. */

                int len = reverseSecondHalfOfList(head);

               

                result = compareList(head, len);

                /** Reverse the second half of linked list to get original list. */

                reverseSecondHalfOfList(head);

           }

           return result == true?"Palindome":"Not Palindrome";

     }

     /**

      * Compare first and second half of list.

      * @param head

      * @param length

      * @return

      */

     private static boolean compareList(Node head, intlength) {

           int counter = 0;

           Node start = head;

           Node end = head;

           Node secHalf = head;

           while(true) {

                if(counter++<length) {

                     end = end.next;

                } else {

                     secHalf = secHalf.next;

                     end = end.next;

                     if(end==null) {

                           break;

                     }

                }

           }

           boolean result = true;

           while(result && secHalf !=null) {

                result = (start.data==secHalf.data);

                start = start.next;

                secHalf = secHalf.next;

           }

           return result;

     }

     /** Reverse the second half of the list. */

     private static int reverseSecondHalfOfList(Node head) {

           Node p1 = head.next;

           Node p2 = p1.next;

           int counter = 0;

           while(p2!=null) {

                counter++;

                p2 = p2.next;

                if(p2==null) {

                     break;

                }

                p1 = p1.next; p2 = p2.next;

           }

           Node start = p1.next;

           Node temp = null;

           Node preNext = null;

           while (start != null) {

                temp = start.next;

                start.next = preNext;

                preNext = start;

                start = temp;

           }

           p1.next = preNext;

           return counter;

     }

     /** Util method to print the List. */

     private static void printList(Node head) {

           if(head==null) {

                System.out.println("List is null");

           }

           if(head.next==null) {

                System.out.print("List : "+head.data+" ");

                return;

           }

           Node next = head.next;

           System.out.print("List : "+head.data+" ");

           while(next!=null) {

                System.out.print(next.data+" ");

                next = next.next;

           }

     }

     /** Driver method. */

     public static void main(String[] args) {

           /*Node head = new Node(1);

           head.next = new Node(2);

           head.next.next = new Node(3);

           head.next.next.next = new Node(4);

           head.next.next.next.next = new Node(3);

           head.next.next.next.next.next = new Node(2);

           head.next.next.next.next.next.next = new Node(1);*/

           Node head = new Node(1);

           head.next = new Node(2);

           head.next.next = new Node(3);

           head.next.next.next = new Node(3);

           head.next.next.next.next = new Node(2);

           head.next.next.next.next.next = new Node(1);

           printList(head);

           String result = checkListIsPalindrome(head);

           System.out.println("\nList is "+result);

     }

}

This method takes O(n) time and O(1) extra space.