• Post Reply Bookmark Topic Watch Topic
  • New Topic

Binary search for Arrays of strings  RSS feed

 
roopa chakra
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi members,

I have two String Arrays: LinArray[]which has 10000 five lettered words
searchArray[] which has 1000 five lettered words

I have to perform a binary search to search 1000 elements in LinArray[].
I don't want to use built in Binary search method.

I know how to perform Binary search on primitives but not on strings.

Could anyone help me out? Thanks.
 
Ernest Friedman-Hill
author and iconoclast
Sheriff
Posts: 24217
38
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You "don't want to" use Arrays.binarySearch? Why not? Is this a homework assignment?
 
roopa chakra
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes it is a home work Assignment.
 
Ernest Friedman-Hill
author and iconoclast
Sheriff
Posts: 24217
38
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
OK, then since you know how to do binary search in an array of numbers, give it a try and show us what you have when you get stuck! It's really the same code. I'll give you a big hint, though: look at the compareTo() method in the String class.

P.S. Binary search is easy to understand, but surprisingly hard to get right. In the real world, you'd always want to use the API method.
 
roopa chakra
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here is my code.
I have taken small example
String lenearArr[]={"tom","brad","bread","lusy");
String searchArr[]={"lusy","brad"};


String midValue;
int mid;
int first=0;
int last=lenearArr.length;
for(int i=0;i<searchArr.length;i++)
{
while(first<last)
{
mid=(first+last)/2;
midValue=lenearArr[mid];
if(searchArr[i].equals(midValue))
{
System.out.println("the element"+searchArr[i]+" found "+mid);
break;
}

int cmp=(searchArr[i].compareTo(midValue));

if(cmp<0)
last=mid;

else
first=mid+1;
}
}

Could you tell me where I am wrong
 
marc weber
Sheriff
Posts: 11343
Java Mac Safari
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A binary search requires sorted data. Otherwise, you have no way of knowing whether your search element is "above" or "below" a midpoint element.
 
roopa chakra
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks.I got the solution.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!