Binary Search

[ReignInChaos]

This can most likely be found on every code site but here is an implementation of binary searching techniques with Strings.

Searching and sorting are some of the biggest topics that are covered in CS classes, especially Data Structures. Sorted structures are the easiest to search on because the programmer already knows how the data is arranged. In this case, I am assuming my List of Strings are sorted from a-z. Here is the recursive code for binary search.

   // recursive binary search
   private int binSrch (int lo, int hi, String target)
   {
        if (lo>hi)
           return -1;           // target not found
        int mid = (lo + hi) / 2;        // midpoint
        if (target.equals(values.get(mid)))
                return mid;     // found the target at mid
        if (target.compareTo(values.get(mid)) < 0 )
                return binSrch (lo, mid-1, target);
        return binSrch (mid+1, hi, target);

  }

This is how it works. It enters the method with a low and high starting value along with a target String. If the target is not found, it returns -1 as the index, then creates the midpoint. Using the .equals() method, it compares the target and the String at the midpoint and returns the mid if found.

Now here is the recursive part. Using the compareTo() method, it will compare target against the String at the midpoint. If target is shorter, it will call binSrch() again with the first half of the List binSrch (lo, mid-1, target);. Otherwise, it will do the same thing with the second half of the list.

[Jordan]

Not bad! +rep.

[chili5]

Nice. How would you go about writing a binary search function that works on any data type?

I do know how to do it, but I'm curious as to how you would do it. =)

+rep for you.

[ReignInChaos]

well if I was using Java I would have binSrch accept an Object as a parameter instead of a String. ie private in binSrch(int lo, int hi, Object obj). I haven't done it but it should work in theory.

[Turk4n]

This can most likely be found on every code site but here is an implementation of binary searching techniques with Strings.

Searching and sorting are some of the biggest topics that are covered in CS classes, especially Data Structures. Sorted structures are the easiest to search on because the programmer already knows how the data is arranged. In this case, I am assuming my List of Strings are sorted from a-z. Here is the recursive code for binary search.

   // recursive binary search
   private int binSrch (int lo, int hi, String target)
   {
        if (lo>hi)
           return -1;           // target not found
        int mid = (lo + hi) / 2;        // midpoint
        if (target.equals(values.get(mid)))
                return mid;     // found the target at mid
        if (target.compareTo(values.get(mid)) < 0 )
                return binSrch (lo, mid-1, target);
        return binSrch (mid+1, hi, target);

  }

This is how it works. It enters the method with a low and high starting value along with a target String. If the target is not found, it returns -1 as the index, then creates the midpoint. Using the .equals() method, it compares the target and the String at the midpoint and returns the mid if found.

Now here is the recursive part. Using the compareTo() method, it will compare target against the String at the midpoint. If target is shorter, it will call binSrch() again with the first half of the List binSrch (lo, mid-1, target);. Otherwise, it will do the same thing with the second half of the list.

Could you possible do for me a special version with a demo ?
It looks really interesting and I would really know more !
rep+

[ReignInChaos]

Sure I'll send you the whole .java file

[Turk4n]

Sure I'll send you the whole .java file

Thank you