roopa chakra

Greenhorn

Posts: 13

posted 12 years ago

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.

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.

roopa chakra

posted 12 years ago

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.

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

posted 12 years ago

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

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

roopa chakra

posted 12 years ago

A binary search requires sorted data. Otherwise, you have no way of knowing whether your search element is "above" or "below" a midpoint element.

"We're kind of on the level of crossword puzzle writers... And no one ever goes to them and gives them an award." *~Joe Strummer*

sscce.org

With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime. |