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 — Tayyab
– Tayyab, Commented Mar 9, 2020 at 12:04
it does but i will write the code on my own, don't want to copy/paste. — Cosmic Dev
– Cosmic Dev, Commented Mar 9, 2020 at 16:59

Eran · Accepted Answer · 2020-03-09 11:15:33Z

0

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.

edited Mar 9, 2020 at 11:15

answered Mar 9, 2020 at 11:09

Eran

395k57 gold badges726 silver badges793 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Cosmic Dev Over a year ago

why not separate logic for odd and even, how will you manage both the cases?

Collectives™ on Stack Overflow

Wrong value while doing Binary Search using Recursion in java

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related