Java and J2EE Tutorials, Jsp and Servlet Tutorials, Spring MVC, Solr, XML, JSON Examples, Hibernate & Struts 2 Hello World projects



Friday, 19 July 2013

Linear and Binary Search Implementation in Java

In this tutorial we will come across 'Search Algorithms in Java ' and their Implementation. Linear Search and Binary Search are two commonly used Search Algorithms used in Java Programming. In this particular blog we will come across their implementation and difference in details.


Linear Search Implementation in Java

Linear Search is the most easiest way of searching elements from an Array or Collection. In this approach we iterate over an Array or collection and  try every element in the collection until we have found the element or until we reach the end of the collection or Array. Here is a simple Java Program to demonstrate working of Linear Search.
package com.beingjavaguys.core;
/**
 *
 * @author Nagesh Chauhan
 */

public class LinearSearch {

 int searchElementLinear(int numList[], int toSearch) {
  int foundIndex = 0;
  for (int i = 0; i < numList.length; i++) {

   if (numList[i] == toSearch) {
    foundIndex = i;
   }
  }
  return foundIndex;
 }
}


Linear Search Complexity in Java

Linear Search iterate over each element until it found the right element hence it has a variable best case and a fixed average and worst case complexity of  'O(n)'.




Binary Search Implementation in Java

Binary search is more efficient and merely used search algorithm in java programming. To implement Binary search we must have an sorted array or collection. Binary Search searches element in middle of the Array. The array is than divided into sub-array in each iteration accordingly, if the element is greater than the middle element or smaller than the middle element the respective sub-array is used for further searching. Here is a simple Java Program demonstrating binary search in Java.
package com.beingjavaguys.core;
/**
 *
 * @author Nagesh Chauhan
 */

public class BinarySearch {

 int searchElementBinary(int numList[], int toSearch) {

  int startIndex = 0;
  int endIndex = numList.length - 1;
  int midindex = (startIndex + endIndex) / 2;
  int midElement = numList[midindex];
  int foundIndex = 0;

  while (startIndex <= endIndex) {
   if (midElement < toSearch) {
    startIndex = midindex + 1;
    midindex = (startIndex + endIndex) / 2;
    midElement = numList[midindex];
   } else if (midElement > toSearch) {
    endIndex = midindex - 1;
    midindex = (startIndex + endIndex) / 2;
    midElement = numList[midindex];
   } else {
    foundIndex = midindex;
    break;
   }
  }
  return foundIndex;
 }

}


Binary Search Complexity  in Java

Binary Search divided the search space into half in each iteration and hence has a 'O(log n)' complexity.


Implementation Class Code

This is a simple java class to demonstrate the actual implementation.

package com.beingjavaguys.core;
/**
 *
 * @author Nagesh Chauhan
 */

public class Implementation {

 public static void main(String args[]) {

  int numList[] = { 1, 3, 8, 12, 34, 56, 78, 87, 92 };
  int toSearch = 12;

  LinearSearch linearSearch = new LinearSearch();
  BinarySearch binarySearch = new BinarySearch();

  System.out.println("Linear Search Index : "
    + linearSearch.searchElementLinear(numList, toSearch));
  System.out.println("Binary Search Index : "
    + binarySearch.searchElementBinary(numList, toSearch));

 }
}



In this particular blog we came across 'Linear and Binary Search in Java' and their Implementation. In upcoming blogs we will come across more about Java and other open source Technologies.







Thanks for reading !
Being Java Guys Team

Download "Binary and Linear Search in Java Example Project" from "SkyDrive"




2 comments:

  1. The implementation of Binary Search contains a potential bug. The bug is in the calculation of mid using:

    int midindex = (startIndex + endIndex) / 2;

    This line effectively says "sets midindex to the average of endIndexand u, truncated down to the nearest integer.". This assertion might appear correct, but it fails for large values of the int variables startIndex and endIndex. Specifically, it fails if the sum of startIndex and endIndex is greater than the maximum positive int value (231 - 1). The sum overflows to a negative value, and the value stays negative when divided by two. In C this causes an array index out of bounds with unpredictable results. In Java, it throws ArrayIndexOutOfBoundsException. So what's the best way to fix the bug?

    Here is one way:

    int midindex = startIndex + ((endIndex- startIndex ) / 2);

    or more faster:


    int midindex = (startIndex + endIndex) >>> 1;

    Cheers.

    ReplyDelete

Like Us on Facebook


Like Us On Google+



Contact

Email: neel4soft@gmail.com
Skype: neel4soft