Monday, March 5, 2012

Linear / Sequential Search and Binary Search in Java

=================Linear Search================
Start from the leftmost element of arr[] and one by one compare x with each element of arr[], if x matches 
with an array element, return the index/location. If x doesn’t match with any of elements, return -1. Array
need not be in Sorted order.

package array;
public class LinearSearch {
    public static void main(String[] args) {
        int array[]={1,4,6,7,9,12,34,56,78,90};

        System.out.println(search(array,5));  // -1
        System.out.println(search(array,4));  //  1
        System.out.println(search(array,90)); //  9
    public static int search(int arr[], int x){
        int i;
        for (i=0; i<arr.length; i++)
            if (arr[i] == x)
                return i;
        return -1;

The time complexity of above algorithm is O(n).

=================Binary Search================
The idea of binary search is to use the information that the array is sorted and reduce the time 
complexity is O(Logn). We basically ignore half of the elements just after one comparison.
1) Compare x with the middle element.
2) If x matches with middle element, we return the mid index.
3) Else If x is greater than the mid element, then x can only lie in right half sub-array after the 
   mid element. So we do recursion for right half.
4) Else (x is smaller) do recursion for the left half.

package array;
import java.util.Arrays;
public class BinarySearch {
    static int ARRAY_UNORDERED = -2;

    public static void main(String[] args) {
        int[] array= {2,3,45,65,31,32,90,5,6,9};
        int x=5;
        System.out.print("Elements After Sorting :");
        for(int i=0;i<array.length;i++) {
            System.out.print(array[i]+", ");
        //Calling binarySearch method
        int element=binarySearch(array,0,array.length-1,x);
        System.out.println("\nPlace Of Element In Array: "+element);
    static int binarySearch(int[] array, int lower, int upper, int target ){
        int center=0;        
        if( array[lower] > array[upper] )
            return ARRAY_UNORDERED;
        center = lower+ (upper-lower)/2;

        if( target == array[center] ){
            return center;
        else if( target < array[center] ){
            return binarySearch( array, lower, center - 1, target );  //Calling binarySearch() recursively
        else {
            return binarySearch( array, center + 1, upper, target );  //Calling binarySearch() recursively
Elements After Sorting :2, 3, 5, 6, 9, 31, 32, 45, 65, 90, 
Place Of Element In Array: 2

Performance: A binary search is O(log(n)) because half of the search is eliminated on each iteration.      

No comments:

Post a Comment