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);
    }
}

i dont understand your problem. what do you mean by I'm having trouble with creating subarrays. — j.con
– j.con, Commented Apr 11, 2014 at 14:56
This is not binary search. When the target lies in the right half of the array, you only increment the start by one. You need start and end in your recursive method. — anonymous
– anonymous, Commented Apr 11, 2014 at 15:02
Take look at algs4.cs.princeton.edu/11model/BinarySearch.java.html for binary search — Mani
– Mani, Commented Apr 11, 2014 at 15:03
And you are assuming the given array is already sorted. if the array is not sorted binary search wont work. Do sort first — Mani
– Mani, Commented Apr 11, 2014 at 15:04

amit · Accepted Answer · 2014-04-11 15:12:05Z

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!

AJMansfield · Accepted Answer · 2014-04-11 15:31:42Z

The very best way to perform that search in Java is this:

Arrays.binarySearch(arr1, start, arr1.length, searchNum);

However, since a reinventing-the-wheel is required for the assignment, you can't just use that. But there are a number of hints you can take from Arrays.binarySearch to help design your program.

One of the main obstacles you are facing here is the method signature you are using:

public static int arraySearch(int start, int searchNum, int [] arr1)

If you were to pattern your method signature off that used by the Arrays.binarySearch method, the task becomes much easier. So you should be implementing something that also allows an end index to be specified. I would also change the argument order to match Arrays.binarySearch, and even call it binarySearch:

public static int binarySearch(int [] a, int fromIdx, int toIdx, int key)

So you should do something like this.

public static int binarySearch(int [] a, int fromIdx, int toIdx, int key){
    if(fromIdx == toIdx) return -1;

    int pivotIdx = (fromIdx + toIdx)/2;

    if(a[pivotIdx] < key) return binarySearch(a, fromIdx, pivotIdx, key);
    if(a[pivotIdx] == key) return pivotIdx;
    if(a[pivotIdx] > key) return binarySearch(a, pivotIdx, toIdx, key);
}

lazarusL · Accepted Answer · 2014-04-11 15:12:32Z

So in your recursive call you will need to only pass an array half the length of the array. You could create a new array with only the first or second half of your array: http://docs.oracle.com/javase/7/docs/api/java/lang/System.html#arraycopy%28java.lang.Object,%20int,%20java.lang.Object,%20int,%20int%29

The other option is to use max and min integers to mark what section of the array you are looking at. If your searchNum is less than the value your are looking at, set max to your start variable. If search Num less than the number you are looking at, set min to start. At the beginning your method, if your current start is <=max or >= min return -1 because you would be searching where you had already looked before therefore the number you are looking for isn't in the array.

beaker · Accepted Answer · 2014-04-11 15:18:12Z

2

Try this:

Add end to your method call as @anonymous suggested.
At each recursive call of ArraySearch, make the values of start and end such that
arr1[start] < searchNum < arr1[end]
And at each recursive call, make the distance between start and end half (roughly) of what it was on the previous call.

answered Apr 11, 2014 at 15:18

beaker

16.9k3 gold badges36 silver badges53 bronze badges

Comments

vran freelancer · Accepted Answer · 2014-05-01 00:27:49Z

I think what you are looking for is something like as mentioned below:

    private int BinarySearch(int[] array, int low, int high, int number)
    {

        // First get the middle index using high and low index 
        int medium = (high + low) / 2;

        // Check if the number you are looking is same as the one at middle index?
        // If that is the case, just return the middle index
        if (array[medium] == number)
        {
           return medium;
        }
        else
        {
            // if the number is not found in previous condition resume the operation. 

            // Check if number is greater than the middle index number 
            if (array[medium] < number)
            {
               // call the search operation by replacing your low index with middle + 1
               return  BinarySearch(array, medium + 1, high, number);
            }
            else
            {
               // Here number is less than the middle index number 
               // call the search operation by replacing your high index with middle-1 
               return  BinarySearch(array, low, medium - 1, number);
            }
        }
    }

Collectives™ on Stack Overflow

Java: Subarrays and Binary search algorithm

5 Answers 5

Comments

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related