Searching

Search is a process of finding a value in a list of values. In other words, searching is the process of locating given value position in a list of values.

---

Types of Searching Techniques

1.      Linear Search

2.      Binary Search

3.      Hash Search

---

Linear Search

Linear search is a simple search where we just compare the searching element with the each value of the array and when matching value find we return the index of that value.

Code snippet-

import java.util.Scanner;

/**

 * This is an implementation of linear search.

 * where we comparing value with each index of array.

 * @author Manoj

 *

 */

public class LinearSearch {

  public static void main(String args[]) {

     int counter, num, item, array[];

     Scanner input = new Scanner(System.in);

     System.out.println("Enter number of elements:");

     num = input.nextInt();

     array = new int[num];

     System.out.println("Enter " + num + " integers");

     for (counter = 0; counter < num; counter++) {

           array[counter] = input.nextInt();

     }

     System.out.println("Enter the search value:");

     item = input.nextInt();

     for (counter = 0; counter < num; counter++) {

         if (array[counter] == item) {

           System.out.println(item + " is present at position " + (counter + 1));

           break;

        }

     }

     if (counter == num) {

           System.out.println(item + " doesn't exist in array.");

     }

   }

}

Note- the worst case complexity of linear search is O (n) because complete array 1-n need to be traversed.

---

Binary Search

In binary search we compare the element with middle element of the array if it’s match than return mid index position if not found then repeat this process with the first half and 2^nd half of the array respectively until each element comparison is not done.

Code Snippet-

/**

 * This is a BinarySearch implementation

 * Compare with the mid element if not found the

 * vice versa with both the half of array

 * @author Manoj

 *

 */

public class BinarySearch {

  public int binarySearch(int[] inputArr, int key) {

     int start = 0;

     int end = inputArr.length - 1;

     while (start <= end) {

           int mid = (start + end) / 2;

           if (key == inputArr[mid]) {

                return mid;

           }

           if (key < inputArr[mid]) {

                end = mid - 1;

           } else {

                start = mid + 1;

           }

     }

     return -1;

  }

  public static void main(String[] args) {

     BinarySearch mbs = new BinarySearch();

     int[] arr = { 1, 3, 6, 8, 9, 10, 12 };

     System.out.println("Key 12'th position: " + mbs.binarySearch(arr, 12));

  }

}

Note – The worst case complexity of Binary search is O (log N)

Explanation - as we need to divide the array in 2 half until it becomes 1

1 = N/2x

2x = N

log 2x = log N (after doing the log2)

x*log2 =log N

x = log N

This means you can divide log N times until you have everything divided