Binary search algorithm

Question

Would this recursive solution's speed be comparable to a non-recursive solution?

// returns location of the target
public static int search(int[] arr, int start, int end, int target){
  int midpoint = (start+end)/2;

  if(target > arr[midpoint])
    return search(arr, midpoint+1, end, target);
  else if(target < arr[midpoint])
    return search(arr, start, midpoint-1, target);
  else
    return midpoint;
}

Answer 1

The expression to calculate a midpoint: (start+end)/2 has a weaknes of potential arithmetic overflow for long arrays (when the maximum index is greater than a half of the maximum integer value).

A safer version: start + (end - start)/2

Answer 2

First The Bug in your code
Your answer wouldn't return the right answer when there is no answer in the array. A valid implementation of recursive binary search in java is following:

 // BinarySearchRecursive: test a recursive version
public class BinarySearchRecursive {

   // need extra "helper" method, feed in params
   public int binarySearch(int[] a, int x) { 
      return binarySearch(a, x, 0, a.length - 1);
   }

   // need extra low and high parameters
   private int binarySearch(int[ ] a, int x,
         int low, int high) {
      if (low > high) return -1; 
      int mid = low + (high - low)/2;//Updated, note in Update one in the end of answer
      if (a[mid] == x) return mid;
      else if (a[mid] < x)
         return binarySearch(a, x, mid+1, high);
      else // last possibility: a[mid] > x
         return binarySearch(a, x, low, mid-1);
   }
   }

It is taken from this site.

---

Note on this kind of Recursion
For implementation of binary search you are using a tail recursion , according to quora answer tail recursion is:

Tail recursion is a special kind of recursion where the recursive call is the very last thing in the function. It's a function that does not do anything at all after recursing.

This is important because it means that you can just pass the result of the recursive call through directly instead of waiting for it—you don't have to consume any stack space. A normal function, on the other hand, has to have a stack frame so that the compiler knows to come back to it (and have all the necessary variable values) after the recursive call is finished. ...

Usually I use recursion as the last resort when using an iterative method and is slightly harder than recursion(some dynamic programming problems in algorithmic programming contests), because of debugging a loop seems a more easy to.But it has performance advantages and you always have to look for your recursion depth to be less than the stack call size (I think the default in Java is 1000).

---

Iterative Method
The code for iterative binary search is from this

// BinarySearch.java: simple implementation
public class BinarySearch {
   // binarySeach: non-recursive
   public int binarySearch(int[] a, int x) {
      int low = 0;
      int high = a.length - 1;
      while (low <= high) {
         int mid = low + (high - low)/2;
         if (a[mid] == x) return mid;
         else if (a[mid] < x) low = mid + 1;
         else high = mid - 1;
      }
      return -1;
   }
}

---

A possible overflow
Update 1: as @CiaPan , I used start + (end - start) / 2 to calculate the result of midpoint, to avoid integer overflow when the array length is more than 1073741823 so start + end is more than integer's max-length( 2^31 - 1), thus preventing a rarely happening but tedious to find bug.

Answer 3

First of all, you should know that you are assuming your target EXISTS inside the array. Otherwise you would be making a non-ending infinite searching loop.

I've developped after 2 hours this example code. It generates an array with Integers and sorts it. Then performs a binary search to find the target, ensuring that it can be found.

For instance, I've needed to use:

System.nanoTime();

for the first time, so I'm NOT sure about I'm catching the right time but aproximately.

The results have been these below, under an array of size 10000000 of Random Sorted int numbers:

// Looping search:
// usually 16.000-17.000 nanos or 6.000-7.000 nanos if before than Recursion
// usually 1500 nanos if after than Recursion

// Recursive search:
// usually 3500 nanos if after than Looping
// usually between 18.000-20.000 nanos or 7.000-9.000 if before than Looping

// why is the second search much faster than the first?
// It might be because after the first time searching the target,
// a large amount of values of the array has been copied into memory.

So I think that Looping might be a little faster than Recursion. It does make sense, since recursion makes use of the thread call stack.

The code has been this below:

//import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

// First of all, you should know that you are assuming your target EXISTS
// inside the array. Otherwise you would be making a non-ending infinite searching loop.
public class ArraySearching {

private static abstract class BinarySearchManager {
    protected abstract int concreteBinarySearch(int arr[], int start, int end, int target);
    public int binarySearch(int arr[], int target) {
        return this.concreteBinarySearch(arr, 0, arr.length-1, target);
    }
}

private static class LoopingBinarySearchManager extends BinarySearchManager {
    @Override
    public int concreteBinarySearch(int[] arr, int start, int end, int target) {
        // assuming that 'arr' contains 'target' 
//      boolean found = false;
        int midpoint;

        do {
            midpoint = (start+end)/2;
            if(arr[midpoint] < target) {
                start = midpoint;
            } else if(target < arr[midpoint]) {
                end = midpoint;
            } else return midpoint;
        } while(true);//arr[start] < target && target < arr[end]);
    }
}

private static class RecursionBinarySearchManager extends BinarySearchManager {
    @Override
    public int concreteBinarySearch(int[] arr, int start, int end, int target) {
         int midpoint = (start+end)/2;
//       System.out.println("Searching the value "+target+" between the position "+start+" and "+end);
         if(target > arr[midpoint]) {
              return concreteBinarySearch(arr, midpoint+1, end, target);
          } else if(target < arr[midpoint]) {
              return concreteBinarySearch(arr, start, midpoint-1, target);
          }
          else return midpoint;
    }

}

public static int size = 10000000; // 1000000000 = java.lang.OutOfMemoryError: Java heap space
public static int numbers[] = new int[size];
// In this case it is not compulsory to pass the array as argument. But you do, so I'll do.
public static Random rand = new Random();
public static BinarySearchManager BSM;
public static int Target;

public static void initializeIntArrayWithRandomNumbers(int arr[]) {

    int randomLimit = Integer.MAX_VALUE;
    for(int i=0; i<arr.length; i++) {
        arr[i] = rand.nextInt(randomLimit);
    }
    System.out.println("Generating an array of "+arr.length+" positions of Random Integers from 0 up to "+randomLimit);
}

public static void sortArray(int arr[]) {
    long beginSortingMillis = System.currentTimeMillis();
    Arrays.sort(arr);
    long endSortingMillis = System.currentTimeMillis();
    long sortingMillis = endSortingMillis - beginSortingMillis;
    System.out.println("Array Sorting Millis: "+sortingMillis);
}

public static void printArray(int arr[]) {
    System.out.println(Arrays.toString(arr));
//      System.out.print("[");
//      for(int i=0; i<arr.length; i++) {
//          System.out.print(arr[i]+", ");
//      }
//      System.out.println("]");
}

public static void main(String[] args) {

    // may be print info about the array (size, numbers scope)
    initializeIntArrayWithRandomNumbers(numbers);
    sortArray(numbers);
//      printArray(numbers);

    Target = numbers[rand.nextInt(size)];

    // Calculating time wasted by Looping search
    BSM = new RecursionBinarySearchManager();
//      long beginLoopingMillis = System.currentTimeMillis();
    long beginLoopingNanos = System.nanoTime();

    BSM.binarySearch(numbers, Target);

//      long endLoopingMillis = System.currentTimeMillis();
    long endLoopingNanos = System.nanoTime();
//      long loopingMillis = endLoopingMillis - beginLoopingMillis;
    long loopingNanos = endLoopingNanos - beginLoopingNanos;
    System.out.println("Looping Nanos: " +loopingNanos);
        // usually 16.000-17.000 nanos or 6.000-7.000 nanos if before than Recursion
        // usually 1500 nanos if after han Recursion
    long loopingMillis = loopingNanos / 1000;
    System.out.println("Looping Millis: " +loopingMillis);


    // ------------------

    // Calculating time wasted by Recursion search
    BSM = new LoopingBinarySearchManager();
//      long beginRecursionMillis = System.currentTimeMillis();
    long beginRecursionNanos = System.nanoTime();

    BSM.binarySearch(numbers, Target);

//      long endRecursionMillis = System.currentTimeMillis();
    long endRecursionNanos = System.nanoTime();
//      long recursionMillis = endRecursionMillis - beginRecursionMillis;
    long recursionNanos = endRecursionNanos - beginRecursionNanos;
//      System.out.println("Recursion Millis: " +recursionMillis); // does not work properly
    System.out.println("Recursion Nanos: " +recursionNanos);
            // usually 3500 nanos if after than Looping
            // usually between 18.000-20.000 nanos or 7.000-9.000 if before than Looping
        long recursionMillis = recursionNanos / 1000;
        System.out.println("Recursion Millis: " +recursionMillis);

    }
}