Course Content‎ > ‎Session 3‎ > ‎

Searching

Search can be performed in two ways:

1. Sequential Search
2. Binary Search

Sequential Search

If list is not ordered or not sorted, then sequential search is the only algorithm that can be used. This search algorithm is very slow. You traverse the list till you find the item or till the end of the list. Assume there is an array called list and target and locn of found item is to be returned. Here is the code, showing the sequential search:

    public int seqSearch (int [] list, int target, int locn) 
    {
        int looker ;
         
        /*Statements*/
        looker = 0;
        while ( looker < last && target != list[looker] )
            looker++ ;
        locn = looker ;
        return ( target == list[looker] ) ;
    }/* seqSearch */ 
    
Binary Search

If the list is ordered or sorted, then we use binary search. Binary search starts off by testing data in the middle of the array. This determines if the target is in the first half or the second half of the array. Whichever half has the element is checked again. The half in which the element does not exist need not be tested again. Repeat the process till element is found.

Three variables are required, identifying the:

  1. beginning of the list
  2. middle of the list
  3. end of the list

Here is the code showing the binary search:

    public int binarySearch (int[] list, int locn, int target)
    {
        int first ;
        int mid ;
        int last ;
         
        /*Statements*/
        first = 0 ;
        last = end ;
         
        while ( first <= last )
        {
            mid = ( first + last ) / 2 ;
             
            /* look in upper half */
            if ( target > list[ mid ] )
                first = mid + 1 ;

            /* look in lower half */
            else if ( target < list[ mid ] )
                last = mid - 1 ;

            /* found equal: force exit */
            else
                first = last + 1 ;

        }/* end while */
         
        locn = mid ;
        return target == list [mid] ;

    }/* binarySearch */

Comments