binary search using recursion [closed]

I implemented a binary search algorithm using recursion in Java package com.soloworld.binarysearch;

/**
*
* @author soloworld
*/
public class BinarySearch {

private int[] array;

public BinarySearch(int[] array) {
this.array = array;
}

public int recursivesearch(int[] array,int startindex,int endindex,int key) {
if(endindex>0) {
int middle =(startindex+ endindex)/2;
System.out.println("middle "+middle);
if(array[middle]== key) return middle;
else if (key <array[middle]) {
return recursivesearch(array, startindex, middle-1, key);
} else if(key > array[middle]) {

return recursivesearch(array, middle+1, endindex, key);
}
}
return -1;
}

}


it worked, all i want to know is have i done it in correct way or there any way to optimize this

closed as off-topic by t3chb0t, Toby Speight, Mast, rolfl♦, GraipherDec 13 '17 at 3:57

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "Questions containing broken code or asking for advice about code not yet written are off-topic, as the code is not ready for review. After the question has been edited to contain working code, we will consider reopening it." – t3chb0t, Toby Speight, Mast, rolfl, Graipher
If this question can be reworded to fit the rules in the help center, please edit the question.

• Please read and follow the Java Naming Conventions - In which aspect do you want to optimize your code? – Timothy Truckle Dec 3 '17 at 17:43
• Did it really work? Did you try it with searching the key 7 in a [1,2] array? – CiaPan Dec 3 '17 at 18:32
• Why is this a class? – Conor Mancone Dec 3 '17 at 22:44
• I have pasted your code into an Online Java IDE compilejava.net and fed the recursivesearch with the example from my comment above. As expected, the results were: middle 0, then 4,848 times middle 1 and then Exception in thread "main" java.lang.StackOverflowError. So your code does '''not''' work and is not ready for code review, according to this site's rules. – CiaPan Dec 11 '17 at 19:33
• What's the point of the (unused) array member? – Toby Speight Dec 12 '17 at 8:56

It's always good to use guard conditions. Instead of wrapping all of your logic in a code block, check for conditions when you don't have to execute and return early. Like so:

public int recursivesearch(int[] array,int startindex,int endindex,int key) {
if (endindex<=0){
return -1;
}

// everything else here
}


It's much easier to read if you structure your code like this: also much less error-prone.

Next, you are missing some guards. What happens if you array is empty? What happens if the value you are looking for is larger or smaller than any values in the array? You have to check for these conditions and handle them individually. You are also trusting that the user has passed a proper index in.

Also, I would make it easier to use by having the public method not require start and end index, calculating them from the length, and then passing it into the actual search method which is protected.

Finally, you were not properly detecting a missing value. You were returning -1 if endIndex<=0, but the proper condition is endIndex<startIndex. Yours ends in an infinite loop for items such as:

recusivesearch([1,2,3,4,6], 0, 4, 5)

Keep in mind that java is not my language of choice, so this might be best viewed as pseudo-code:

public int search(int[] array, int key) {
if (array.length == 0){
return -1;
}

if (key < array[0] || key > array[array.length-1]){
return -1;
}

return this.recursiveSearch(array, key, 0, array.length-1);
}

protected int recursiveSearch(int[] array, int key, int startIndex, int endIndex){
if (endIndex<startIndex){
return -1;
}

int middleIndex = startIndex + (endIndex-startIndex)/2;
if (array[middleIndex] == key){
return middleIndex;
}
if (key < array[middleIndex]){
return recursiveSearch(array, key, startIndex, middleIndex-1);
}
return recursiveSearch(array, key, middleIndex+1, endIndex);
}


Nitpicks

Your definition of middle was prone to integer overflow. I adjusted the definition to fix that issue.

Watch out for your use of whitespace. In the long run, consistent whitespace makes code maintenance much easier. Java problem has some general standards, which I'm guessing at.

Same with capitalization. I believe Java prefers camelCase. Some people prefer snake_case. Pick one and stick to it: you don't do either, and it makes it harder to read your variable names.

Naming variables is also important. You have startindex and endindex, and then middle. You should at least go for consistency:

startIndex, endIndex, middleIndex

Or

start, end, middle

Since these variables contain indexes, I would probably go for the former, but for shorter names I would also consider the latter acceptable. Either way, Keep your names consistent.

• Good points! I think the protected method will not compile due to the compiler thinking there is still a path without a return. I personally also use plain if-statements instead of else-if when a previous if-block has a return (in all cases). And I'd even remove the last if-statement all together, directly returning the last possible case. – Koekje Dec 4 '17 at 18:55
• Thanks: the logic is such that a return is guaranteed to happen, but I like having it explicitly stated too. Regarding if-return-else-if, I get conflicted. Sometimes I like to have the if-else-if because it better reflects the logic, but when you have an if-return then there really isn't much point in an elseif. I'll go with the latter logic for now. – Conor Mancone Dec 4 '17 at 19:04
• The tests in search() protect you against some very special cases, and catch nothing in normal, reasonable operation. And the same special cases will be normally caught by the endIndex<startIndex test in recursiveSearch() after some iterations. So, both if-s in the search() function are generally unnecessary. – CiaPan Dec 6 '17 at 16:24
• @CiaPan True story. I usually start from the perspective of "What conditions should I watch out for" and didn't notice that the condition checked inside the main loop actually covers everything. That being said, the other issue is that making startIndex and endIndex optional would probably be better than having a separate method to call. My brief googling in Java suggested that optional parameters don't exist, so I don't know if there is a different "standard" way to handle that. – Conor Mancone Dec 6 '17 at 17:17
• @ConorMancone I think you're right. And that's precisely the reason I wrote those two conditions in the search() function are superfluous, not the search() itself. – CiaPan Dec 6 '17 at 20:11

No, there is no way to optimize the code, yet.

There is. however, a way to fix it, so that it will correctly perform searching
e.g. 7 in an array [1, 2].