DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

# Thread: Using Binary Search switching to Sequential search

1. Registered User
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. Senior Member
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.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

 FAQ Latest Articles Java .NET XML Database Enterprise