DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 2 of 2

Thread: Using Binary Search switching to Sequential search

  1. #1
    Join Date
    Mar 2007
    Posts
    3

    Using Binary Search switching to Sequential search

    Code:
    	
    public int binarySeqSearch(int key)
    {
       int first = 1;
       int last = list.length-1;
       int mid = -1;
       boolean found = false;
       comparisons = 0;
    			
    	while (first <= last &&!found) 
    	{
                  	mid = (first + last) /2;
                              if (list[mid] == key) 
    	{
    		found = true;
                   	comparisons = comparisons + 1;
                   	return mid;
                	}
                	else if (list[mid] < key && key >0 ) 
    	{
                   	comparisons = comparisons + 2;
                   	first = mid + 1;
    		if (list.length<15)//This is where I think I need something different???
    		seqSearch(key);
                	}
                	else 
    	{
                   	comparisons = comparisons + 2;
                   	last = mid - 1;
    						
    	}
    }
    return -1;
    }
    		
    		//Method seqSearch does a sequential search when the list is less than 15
    public int seqSearch(int key)
    {
       comparisons = comparisons;      
       boolean done = false;
       for (int i = 0; i < list.length; i++) 
       {
    	++comparisons;
            	if (list[i] == key) 
             	{   // found the key
    	     return i; 
    	}
    	if  (list[i] != key) 
    	{               
                	     return -1;  
            	}
       }
       return -1;
    }
    I was trying to use binarySearch to search the list switching to the sequential search when the size of the search list reduces to less than 15 (on a sorted list of ints). I'm trying to see what the comparisons would be using it this way vs. just using binary. I got the binary to work but not binary switching to sequential when < 15. Any helpful tips would be appreciated. Ive tried several different things and can't seem to get this to work correctly.

  2. #2
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    A recursive approach to doing search is to pass the structure you are searching, and the index of low and high, as the arguments to your search method. Were you to do that, you could check the size, and if the size < 15 then use sequential search.

    Code:
    int binarySearch( List list, int low, int high, key)
    {
         mid = floor((high-low)/2)
         if list[mid] == key  end search return mid
         else
         {
             if( (high-low + 1) < 15 )
            {
                return sequentialSearch( list, low, high, key );
            }
            else
            {
                if (if key > list[mid] )
                {
                    return binarySearch( list, mid+1, high, key )
                }
                else
                {
                    return binarySearch( list, low, mid-1, key )
                }
             }
         }
    }

    With your setup, if you were to put
    Code:
    test:  does mid == key? if not, then
    
    if( (last - first + 1) < 15 )
    {
        call sequential search
    }
    else
    { 
        if key > list[mid]
        {
             low = mid+1
        }
        else 
        {
             high = mid-1;
        } 
    }
    you'd switch to sequential search when the sequence you are searching falls below 15 elements long.
    Last edited by nspils; 04-03-2007 at 11:02 AM.

Similar Threads

  1. Binary and Linear Search
    By ForlornSpawn in forum Java
    Replies: 1
    Last Post: 04-07-2006, 02:43 PM
  2. Binary Search Tree Search algorithm
    By spazzzer in forum Java
    Replies: 1
    Last Post: 03-20-2006, 06:45 PM
  3. Search algorithm of the Binary Search Tree
    By spazzzer in forum Java
    Replies: 6
    Last Post: 03-20-2006, 03:37 AM
  4. How to implement binary search
    By WXY595 in forum Java
    Replies: 2
    Last Post: 02-17-2006, 04:21 PM
  5. Binary Search Tree implementation
    By Liza in forum Java
    Replies: 0
    Last Post: 10-23-2001, 11:21 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center