CODEWITHSUNDEEP
javabinary-search
Nervoxin
Nervoxin

Reputation: 13

How do you use a binary search using only words and not numbers?

I was asked to use binary search to find specific words in a file that we read.

The issue I do not understand is how to use a binary search when you are looking for words and not numbers.

Upvotes: 1

Views: 5692

Answers (3)

krpra
krpra

Reputation: 464

Binary Search for string Implemented in C.

    char *lineptr[MAXLINE]  //Array of char pointers stores the address of string
    int binsrch(char srch[],int low,int high)
    {
       int mid;

       if(high>=low){
          mid=(low+high)/2;
          if(strcmp(srch,lineptr[mid])<0) //compare string stored in srch and lineptr[mid]
                return binsrch(srch,low,mid-1,count);
          else if(strncmp(srch,lineptr[mid],count)>0)
               return binsrch(srch,mid+1,high,count);                                                      
          else 
               return mid; // Found
       }
     return -1;  //Not found
  }

Upvotes: 0

noel
noel

Reputation: 2339

Think of looking up a word in the dictionary; this is an example of binary search.

For example, lets look up "eunoia":

  1. You flip open the dictionary to approximately the "E" section but maybe you go a little too far and end up in the "M" section.
  2. You flip about half way back and now you're in the "E" section (if you're lucky)
  3. Move onto the next letter in the word and repeat.

This all works because the dictionary is well-ordered, we all agree that A is the 1st letter, B is the 2nd, etc. Another way to look at it is that the Alphabet is the same thing as the numbers [0 - 25] just with different names.

Upvotes: 1

Zabuzard
Zabuzard

Reputation: 25903

Binary search operates on sorted inputs. You can define an order also on words, not only on values.

For example the lexicographical order. In Java this is even implemented as the natural order of Strings. So you can do "text1".compareTo("text2") and it returns the order.

A small illustration of binary search:

Binary search illustration

As you see, the only thing to decide in the algorithm is the order between two objects. For example, from the image, 7 < 14 and 7 > 6. As said, you can also do this for Strings. Indeed for everything for which you define an order.

Actually many classes in Java (more than 150) implement a natural order, they are listed under the interface Comparable (documentation), they all provide a compareTo method with a meaningful order.

Upvotes: 5

Related Questions