Java: Subarrays and Binary search algorithm

Question

I must create a program that searches for an int in arr1 by a binary search algorithm and return -1 if the int isn't found. I'm having trouble with creating subarrays. It works at the moment without them but I've only a workaround for whenever the int is greater than start.

public class Question8p2 {
    public static void main(String[] args){
        int[] arr1 = {2,45,234,567,876,900,976,999};
        int start = arr1.length / 2;
        int searchNum = 900;
        arraySearch(start, searchNum, arr1);
        System.out.println(arraySearch(start, searchNum, arr1));
    }

    public static int arraySearch(int start, int searchNum, int [] arr1){
        if (arr1[start] == searchNum){
            return start;
        }

        if (arr1[start] < searchNum){
            start = start + 1;
        }

        if (arr1[start] > searchNum){
            start = start / 2;
        }

        if (start == arr1[0] || start == arr1.length){
            return -1;
        }

        return arraySearch(start, searchNum, arr1);
    }
}

Answer 1

First to answer your question - you can create a sub-array by using Arrays.copyOfRange(array,from,to)..

However, this is NOT what you want to do. Creating a subarray this way is O(n) (recall that it is a copy..), and you don't want to do it.

Instead, use arguments in your method, start and end - that indicate the range your binary search is looking for now.

Also note that increasing by 1 when the element is not found is not binary search, instead you need to design your algorithm that it will always 'jump' by half of the remaining array - and not by a constant size.

According to this, your method signature will be something like:

public static int arraySearch( int [] arr1, int start, int end, int searchNumber){ ... }

You will then set a mid element: int mid = start + (end - start)/2;
And you will check if the required number is bigger than arr1[mid] or not.
If it is, you will recurse with arraySearch(arr1,mid+1,end,searchNumber), and if it is smaller you will recurse with arraySearch(arr1,start,mid,searchNumber)

Hope that clarifies how your binary search should be implemented.
Good Luck!