/* Example of divide and conquer.
 * Use recursion to rapidly find the sum of an array, or to find an element
 * in an array.
 */
import java.io.*;

public class Conquer
{
  static int [] a = { 4, 6, 2, 8, 3, 0, 9, 1, 5, 3,
                      9, 1, 4, 2, 0, 7, 3, 8, 1, 6,
                      3, 8, 19, 4, 6, 5, 5, 1, 2, 9,
                      8, 7, 5, 9, 0, 1, 5, 3, 4, 6 };

  public static void main(String [] args) throws IOException
  {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    System.out.printf("Enter a number to search for:  ");
    int key = Integer.parseInt(in.readLine());

    int location = search(key, a, 0, a.length - 1);
    System.out.printf("The search returned location:  %d\n", location);

    int sum = sum(a, 0, a.length - 1);
    System.out.printf("Sum of array is %d\n", sum);
  }

  // Search for a number 'key' in an array 'a', in that part of the
  // array from begin..end only.  If not found, return -1.
  // To do this recursively, if begin==end, then check to see if
  // we are pointing at the element.
  // If begin < end, then we call ourselves recursively to cut
  // the search space in half.
  public static int search(int key, int [] a, int begin, int end)
  {
    System.out.printf("Looking at range %d..%d\n", begin, end);

    // The happy base case:  we found it!
    if (begin == end && a[begin] == key)
	return begin;

    // The unhappy base case:  it's not here.
    else if (begin == end)
	return -1;

    // Otherwise look in the first half... If not there, try 2nd half.
    int midpoint = (begin + end) / 2;
    int location = search(key, a, begin, midpoint);

    if (location != -1)
	return location;
    else
      return search(key, a, midpoint + 1, end);
  }

  // Now, using the divide & conquer strategy, find sum of array elements.
  public static int sum(int [] a, int begin, int end)
  {
    if (begin == end)
      return a[begin];
    else
    {
      int midpoint = (begin + end) / 2;
      return sum(a, begin, midpoint) + sum(a, midpoint + 1, end);
    }
  }
}