Searching is a fundamental activity in computing. Lot of activities rely on searching techniques. Two searching techniques are included in the ICSE/ISC syllabus, viz.: linear searching and binary searching.

Linear search is used when the numbers are not sorted and binary search is preferred when the elements are searched in ascending or descending order.

Linear searching

In computer science, linear search or sequential search is a method for finding a particular value in a list, that consists of checking every one of its elements, one at a time and in sequence, until the desired one is found. Linear search is the simplest search algorithm; it is a special case of brute-force search. It’s preferred when the number of elements to be searched for are limited.

Linear search can be implemented in Java programming language as follows:

class Searching{
    public static int linearSearch( int a[], int item ){
        int position = -1;
        for( int i=0 ; i < a.length ; i++ ){
            if( a[ i ] == item ){
                position = i;
                break;
            }
        }
        return position;
    }
    public static void main( String args[] ){
        int a[] = { 4, 6, 3, 4, 7, 8, 1, 2, 3 };
        int position = linearSearch( a, 38 );
        if( position == -1 ){
            System.out.println( "Item not found." );
        }else{
            System.out.println( "Item found at index: " + position );
        }
        position = linearSearch( a, 3 );
        if( position == -1 ){
            System.out.println( "Item not found." );
        }else{
            System.out.println( "Item found at index: " + position );
        }
    }
}

The above program using linear search would return the first index position (0 based) at which the item is located. The function linearSearch( ) would return -1 to indicate the absence of the item in the array.

Binary searching

A binary search or half-interval search algorithm finds the position of a specified input value (the search “key”) within an array sorted by key value. For binary search the array should be arranged in ascending or descending order. In each step, the algorithm compares the search key value with the key value of the middle element of the array. If the keys match, then a matching element has been found and its index, or position, is returned. Otherwise, if the search key is less than the middle element’s key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the search key is greater, on the sub-array to the right. If the remaining array to be searched is empty, then the key cannot be found in the array and a special “not found” indication is returned.

A binary search halves the number of items to check with each iteration, so locating an item (or determining its absence) takes logarithmic time.

class BinarySearching{
    public static int binarySearch( int a[], int item ){
        int lowerBound = 0, upperBound = a.length -1, mid;
        while( lowerBound <= upperBound ){
            mid = ( lowerBound + upperBound ) / 2;
            if( item == a[ mid ]) return mid;
            else if( item < a[ mid ] ) upperBound = mid -1;
            else lowerBound = mid + 1;
        }
        return -1;
    }
    public static void main( String args[] ){
        int a[] = { 1, 2, 5, 7, 9 , 10, 13, 15 };
        int position = binarySearch( a, 13 );
        if( position == -1 ){
            System.out.println( "Item not found." );
        }else{
            System.out.println( "Item found at index: " + position );
        }
        position = binarySearch( a, 3 );
        if( position == -1 ){
            System.out.println( "Item not found." );
        }else{
            System.out.println( "Item found at index: " + position );
        }
    }
}

 

Following content is relevant for ISC students only.

Recursive Linear searching

Linear search can also be implemented recursively (with memory and performance overheads) in Java programming language as follows:

class Searching{
    private static int linearSearchRecursive( int a[], int item, int from ){
        if( from == a.length ) return -1;
        else if( a[from] == item ) return from;
        else return linearSearchRecursive( a, item, from+1 );
    }
    public static int linearSearchRecursive( int a[], int item ){
        return linearSearchRecursive( a, item, 0 );
    }
    public static void main( String args[] ){
        int a[] = { 4, 6, 3, 4, 7, 8, 1, 2, 3 };
        int position = linearSearchRecursive( a, 38 );
        if( position == -1 ){
            System.out.println( "Item not found." );
        }else{
            System.out.println( "Item found at index: " + position );
        }
        position = linearSearchRecursive( a, 3 );
        if( position == -1 ){
            System.out.println( "Item not found." );
        }else{
            System.out.println( "Item found at index: " + position );
        }
    }
}

 

Recursive Binary searching

Binary search can also be implemented recursively (with memory and performance overheads) in Java programming language as follows:

class BinarySearching{
    private static int binarySearchRecursive( int a[], int item, int lowerBound, int upperBound){
        if( lowerBound > upperBound ) return -1;
        int mid = ( lowerBound + upperBound ) / 2;
        if( item == a[ mid ] ){
            return mid;
        }else if( item < a[ mid ] ){
            return binarySearchRecursive( a, item, lowerBound, mid - 1);
        }else{
            return binarySearchRecursive( a, item, mid + 1, upperBound);
        }
    }
    public static int binarySearchRecursive( int a[], int item ){
        return binarySearchRecursive( a, item, 0, a.length);
    }
    public static void main( String args[] ){
        int a[] = { 1, 2, 5, 7, 9 , 10, 13, 15 };
        int position = binarySearchRecursive( a, 13 );
        if( position == -1 ){
            System.out.println( "Item not found." );
        }else{
            System.out.println( "Item found at index: " + position );
        }
        position = binarySearchRecursive( a, 3 );
        if( position == -1 ){
            System.out.println( "Item not found." );
        }else{
            System.out.println( "Item found at index: " + position );
        }
    }
}