Binary search

Do a binary search through a sorted integer array for a certain number. Implementations can be recursive or iterative (both if you can). Print out whether or not the number was in the array afterwards. If it was, print the index also. The algorithms are as such (from the wikipedia):

Recursive:

  BinarySearch(A[0..N-1], value, low, high) {
      if (high < low)
          return not_found
      mid = (low + high) / 2
      if (A[mid] > value)
          return BinarySearch(A, value, low, mid-1)
      else if (A[mid] < value)
          return BinarySearch(A, value, mid+1, high)
      else
          return mid
  }

Iterative:

  BinarySearch(A[0..N-1], value) {
      low = 0
      high = N - 1
      while (low <= high) {
          mid = (low + high) / 2
          if (A[mid] > value)
              high = mid - 1
          else if (A[mid] < value)
              low = mid + 1
          else
              return mid
      }
      return not_found
  }

Iterative

	...
	//check will be the number we are looking for
	//nums will be the array we are searching through
	int hi = nums.length - 1;
	int lo = 0;
	int guess = (hi + lo) / 2;
	while((nums[guess] != check) && (hi > lo)){
		if(nums[guess] > check){
			hi = guess - 1;
		}else if(nums[guess] < check){
			lo = guess + 1;
		}
		guess = (hi + lo) / 2;
	}
	if(hi < lo){
		System.out.println(check + " not in array");
	}else{
		System.out.println("found " + nums[guess] + " at index " + guess);
	}
	...