I did some research and wasn't able to find anything but if this is a duplicate please let me know.
I have this code for binary search of integers
package thepac;
public class CustomBS{
public static void main(String[] args){
int[] listOfNumbers = new int[]{2,45,65,76,89,100,342,455};
int numberToSearch = 100;
int lowestIndex = 0;
int highestIndex = listOfNumbers.length-1;
int middleIndex;
while(lowestIndex<=highestIndex){
middleIndex = (lowestIndex+highestIndex)/2;
if(numberToSearch > listOfNumbers[middleIndex]){
lowestIndex = middleIndex+1;
}else if(numberToSearch < listOfNumbers[middleIndex]){
highestIndex = middleIndex-1;
}else{
break;
}
}//end of while
if(lowestIndex > highestIndex){
System.out.println("not found");
}else{
System.out.println("found");
}
}
}
This works just find and I understand the concept. Is it possible to implement a version of this that searches for Strings as in an array of Strings?
I can't think of how to implement this since the current algorithm checks if the number being searched is higher or lower than the middle index, but if it's a String, how do I check if it's higher or lower than another string?
I know I can use the String.compareTo() method to check if a string is larger or shorter than another one but I'm not sure if this would be the correct way of implementing this.
If you have two strings s1 and s2 then
s1.compareTo(s2)
returns a negative result if s1 is lexicographically smaller than s2, a positive result if s1 is lexicographically bigger than s2 and 0 if they are equal.
So you can write your function like this:
public static void main(String[] args){
String[] listOfStrings = new String[]{"a","b","c","d","g","h","k","z"};
String stringToFind = "d";
int lowestIndex = 0;
int highestIndex = listOfStrings.length-1;
int middleIndex = 0;
while(lowestIndex<=highestIndex){
middleIndex = (lowestIndex+highestIndex)/2;
if(stringToFind.compareTo(listOfStrings[middleIndex]) > 0){
lowestIndex = middleIndex+1;
}else if(stringToFind.compareTo(listOfStrings[middleIndex]) < 0){
highestIndex = middleIndex - 1;
}else{
break;
}
}//end of while
if(lowestIndex > highestIndex){
System.out.println("not found");
}else{
System.out.println("found at " + middleIndex);
}
}
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments