I am trying to do my assignment. I think that I am really close to solving it, but I can't do it.. I've been trying to do it for last several hours.
What I am trying to do: I have a string and a char. I am trying to implement the binary search to look for a char, but it doesn't return the value that I want. Well it is correct, but I want this code to return 5 instead of 4.
This is my code, can You help me to solve it? There is no sort method, because I didn't want the code in here to be super long, but please assume that sorting method sorts correctly. If you'd like to see the sorting method then I am able to upload it for you.
I would appreciate any kind of help, because I've spent way to much time for it.. :/.
public static void main(String[] args) {
String s = "abcdefg";
char c = 'e';
System.out.println(findRecursiveD(s, c));
}
public static int binarySearch(char[] a, char c, int start, int end) {
int mid = (start + end) / 2;
if(a[mid] == c)
return mid;
else if (a[mid] < c)
return binarySearch(a, c, mid+1, end);
else
return binarySearch(a, c, start, mid);
}
public static int findRecursiveD(String s, char c) {
int start = 0;
String S = s + c;
char[] b = S.toCharArray();
int end = b.length;
sort(b, 0, end);
String A = new String(b);
System.out.println(A);
return binarySearch(b, c, start, end);
}
}
Your code is actually correct, but your concept of what the correct index is may be off. Arrays in Java are zero-indexed, which means the first element of the array actually is 0, not 1. So in the character array you provided, e is the fifth element, but that means that to access it, you would do s[4] to reference it.
If you really want to return 5 instead of 4, you should just add one to your answer.
USe this:
System.out.println(findRecursiveD(s, c) + 1);
You need to add one, because the 5th position in the string is position 4. The first position int eh string is numbered 0. 4 is the correct answer if you want the number of the position. But if you want to count starting with 1, then you need to add one.
Also, you need to terminate searching when start == end. You will run into bad problems is start+1 is greater than end, so you should test for, and avoid this situation. When start == end, then after to verify that the character at position mid (== start == end) is not c, then check for this condition and return something special, like -1, or throw an exception.
public static int binarySearch(char[] a, char c, int start, int end) {
int mid = (start + end) / 2;
if(a[mid] == c) {
//now search for the 'last' character of that value
while (mid+1<a.length && a[mid+1]==c) {
mid++;
}
return mid;
}
else if (start==end) {
//if no character of that value found
return -1;
}
else if (a[mid] < c) {
return binarySearch(a, c, mid+1, end);
}
else {
return binarySearch(a, c, start, mid);
}
}
And remove the statement that adds a character into the string being searched. I don't see why that overhead of adding in a value helps, and it seems like a bad coding practice to learn anyway to modify the search data before you search it.
