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: http://stackoverflow.com/questions/19012677/how-to-use-recursion-in-creating-a-binary-search-algorithm — momar, Dec 11 '15 at 14:29
You should compare strings using `.equals`, not `==`. See [this question](http://stackoverflow.com/questions/513832/how-do-i-compare-strings-in-java). — Kenney, Dec 11 '15 at 14:30
I think your issue might be more about a need to understand recursion? — code_dredd, Dec 11 '15 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, Dec 11 '15 at 14:36
If I put this method in my code: recursiveBinarySearch(nums, arrayFirst, arrayEnd, IOTools.readString("Is your number or higher ?[You can answer: yes or higher] ")); It doesn't work after I updated if (question.equals("higher")) and if (question.equals("lower")) — Anna K, Dec 11 '15 at 14:39
You should put `String question = IOTools.readString("Is your number "+nums[s] + " or higher ?[You can answer: yes or higher] ");` in the first line of the function recursiveBinarySearch and delete the argument 'question', since then it is no longer needed. Now the program asks the user after every step for new input. — Robin Spiess, Dec 11 '15 at 14:42
And the arguments you pass to the function are actually also wrong. If the user inputs "higher" you want to search in the upper half of the sorted array and vice-versa. (you currently do the opposite) — Robin Spiess, Dec 11 '15 at 14:53

score 0 · Answer 1 · answered Dec 11 '15 at 14:43

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

score 0 · Answer 2 · answered Dec 11 '15 at 15:00

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

recursion method in the binary search

2 Answers2