Wrong value while doing Binary Search using Recursion in java

Question

I am trying to implement binary search using recursion but i am not getting the correct results as expected. Here's the code:

import java.util.*;
class BinarySearchRecursion{

    static private int searchNum(int[] array, int item){
        if(array.length >=2){
            int remainder = array.length%2;
            int splitSize = array.length/2;
            if(remainder==0){
                if(item> array[splitSize-1]){
                    int num = searchNum(Arrays.copyOfRange(array,splitSize,array.length), item);
                    return num;
                }else{
                    int num = searchNum(Arrays.copyOfRange(array,0,splitSize), item);
                    return num;
                }
            }else{
                if(array[splitSize]== item)
                    return splitSize;

                if(item> array[splitSize-1]){
                    int num = searchNum(Arrays.copyOfRange(array,splitSize,array.length), item);
                    return num;
                }else{
                    int num = searchNum(Arrays.copyOfRange(array,0,splitSize), item);
                    return num;
                }
            }
            //System.out.println(splitSize);
        }else{
            if(array[0] == item){
                System.out.println("Item exist");
                return item;
            }
            else
                return -1;
        }
        //return -1;
    }


    public static void main(String... args){
        int[] arr = {1,2,3,4,5,6,7,8,9,10};
        int index = searchNum(arr, 89);
        if(index != -1){
            System.out.println("Number exist: "+ Integer.valueOf(index));
        }
        else
            System.out.println("Number does not exist in the given list.");
    }
}

I am not getting the correct items, like if i search for 8 it give me value 2,etc. What i am doing wrong here?

Does this answer your question? [How to use recursion in creating a binary search algorithm](https://stackoverflow.com/questions/19012677/how-to-use-recursion-in-creating-a-binary-search-algorithm) — Tayyab, Mar 09 '20 at 12:04
it does but i will write the code on my own, don't want to copy/paste. — Cosmic Dev, Mar 09 '20 at 16:59

Eran · Answer 1 · 2020-03-09T11:15:33.650

You are trying to search for the index of a given number in the array, but since your recursive method keeps passing sub-arrays to the recursive calls, the indices keep changing.

For example, when you call

searchNum(Arrays.copyOfRange(array,splitSize,array.length), item)

Index splitSize of the current array will become index 0 of the new array passed to searchNum().

You should always pass the original (full) array to the recursive calls, and in addition you should pass the first and last indices of the relevant range.

Another error in your code is in the if(array[0] == item) condition, where you return the item value instead of the index of that item.

Other than that, you probably don't have to write separate logic for the case of odd vs. even range of the array.

why not separate logic for odd and even, how will you manage both the cases? — Cosmic Dev, Mar 09 '20 at 16:57

Wrong value while doing Binary Search using Recursion in java

1 Answers1