recursion method in the binary search

Question

I'm trying to implement a binary algorithm but I really don't know how to write this program using a recursion method. Could someone help me please write this method? I have already written the easiest way for me:

import Prog1Tools.IOTools;
public class BinarySearch {

     public static void showArray(int[] array) {
         for(int x : array) System.out.print (x + " ");
         System.out.println ();
         }

     public static void fillArray(int[] array, int arrayFirst) {
         int i = 0;     
         while (i < array.length){
             array[i] = arrayFirst;
             i++;
             arrayFirst++;
         }   
    }

     public static void main(String[] args) {

         int l, p, s;
         int arrayEnd = IOTools.readInt("Type a last number in the array : ");
         int arrayFirst = IOTools.readInt("Type a first number in the array : ");         
         int[] nums = new int[arrayEnd+1-arrayFirst ];  
         fillArray(nums, arrayFirst);
         showArray(nums);    
         System.out.println ("Could you please choose a number from the array above? " );  
         l = 0;
         p = arrayEnd-arrayFirst;
         loop: while (l <= p) {
              s = (l + p) / 2;
              String question = IOTools.readString("Is your number "+nums[s] + " or higher ?[You can answer: yes or higher] ");

                switch (question){
                case "yes":
                    System.out.println("I found a number "+nums[s]+" Your number has an index "+s +" in the array");
                    break loop;
                case "higher":
                    l = s + 1;  
                    break; 
                }               
              }
          }  
     }

I tried such method but it doesn't work

    public static int recursiveBinarySearch(int[] sortedArray, int start, int end, String question) {

        if (start < end) {
            int mid = start + (end - start) / 2; 
            if (question=="higher") {
                return recursiveBinarySearch(sortedArray, start, mid, question);

            } else if (question=="lower") {
                return recursiveBinarySearch(sortedArray, mid+1, end , question);

            } else {
                return mid;  
            }
        }
        return -(start + 1); 
    }

Possibly the same question as this: stackoverflow.com/questions/19012677/… — momar
– momar, Commented Dec 11, 2015 at 14:29
You should compare strings using .equals, not ==. See this question. — Kenney
– Kenney, Commented Dec 11, 2015 at 14:30
I think your issue might be more about a need to understand recursion? — code_dredd
– code_dredd, Commented Dec 11, 2015 at 14:34
See if it works when you use if (question.equals("higher")) and if (question.equals("lower")). And you also need to update the question variable. — Robin Spiess
– Robin Spiess, Commented Dec 11, 2015 at 14:36

Bob · Accepted Answer · 2015-12-11 14:43:14Z

0

public boolean binaryS(int A[],int left, int right, int x){
    int middle;
    //check if there is any array left to search
    if (left > right) return false;
    //determine the middle of this array section
    middle = (left + right) / 2;
    //is the middle what we are looking for?
    if (A[middle] == x) return true;
    //search the half of the array that might contain x
    if (A[middle] > x) { //search for x to the left
        return binaryS(A, left, middle - 1, x);
    } else { //search for x to the right
        return binaryS(A, middle + 1, right, x);
    }
}

answered Dec 11, 2015 at 14:43

Bob

1

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

Comments

Robin Spiess · Accepted Answer · 2015-12-11 15:00:00Z

Bob's answer is a nice binary search.

If you want to have user input (and keep your structure):

public static int recursiveBinarySearch(int[] sortedArray, int start, int end) {
    if (start < end) {
        int mid = (start + end) / 2;
        String question = IOTools.readString("Is your number compared to "+sortedArray[mid] + " lower or higher?[You can answer: equal, lower or higher] "); 
        if (question.equals("higher")) {
            return recursiveBinarySearch(sortedArray, mid+1, end, question);
        } else if (question.equals("lower")) {
            return recursiveBinarySearch(sortedArray, start, mid-1, question);
        } else {
            return mid;  
        }
    }
    System.out.println("Something went wrong...");
    return -1;
}

Collectives™ on Stack Overflow

recursion method in the binary search

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related