Binary search on a Bitonic array

Question

So, I have been preparing for an interview and I thought of coding up a Binary search on a Bitonic array for practice. A bitonic array has a bunch of numbers in increasing order at the beginning of the array and then a bunch of numbers in decreasing order after that. And the problem is to find out whether or not a number exists in the Bitonic array.

import java.util.Arrays;
import java.util.Scanner;
import java.util.Collections;
public class Bitonic{
 private Integer[] array;
 // This is the maximum possible number in the array.
 private int maxPossibleValue = 45645454;
 public Bitonic(int n, int inv)
 {
 // Make a n element array and initialize each position with a random value.
 array = new Integer[n];
 for(int i = 0; i < n; i++){
 array[i] = (int)Math.floor(Math.random() * maxPossibleValue);
 }
 // inv is the inversion point where the numbers stop increasing and start decreasing.
 // To make this artificially happen, I sorted one half of the array in ascending order
 // And the other half in descending.
 Arrays.sort(array, 0, inv);
 Arrays.sort(array, Math.min(inv + 1, n), n, Collections.reverseOrder());
 // Print the array.
 System.out.println(Arrays.toString(array)); 
 }
 private int finder(int target, int start, int end){
 System.out.printf("Processing: %d to %d\n", start, end);
 int currentPoint = (int)Math.floor(end + start)/2;
 int left = Math.max(start, currentPoint - 1);
 int right = Math.min(end, currentPoint + 1);
 int leftValue = array[left];
 int rightValue = array[right];
 int currentValue = array[currentPoint];
 if(currentValue == target){
 System.out.println("Found the value.");
 return currentPoint;
 }
 if(start == end && currentValue != target){
 return -1;
 }
 if(currentValue > leftValue && currentValue < rightValue){
 // Behind inversion point.
 if(currentValue < target){
 return finder(target, right, end);
 }
 else{
 int result = finder(target, start, left);
 if(result != -1){
 return result;
 }
 return finder(target, right, end);
 }
 }
 else if(currentValue < leftValue && currentValue > rightValue){
 // After inversion point.
 if(currentValue < target){
 return finder(target, start, left); 
 }
 else{
 int result = finder(target, right, end);
 if(result != -1){
 return result;
 }
 return finder(target, start, left);
 }
 }
 else{
 // At inversion point or at one of the extreme corners or a plateau.
 int result = finder(target, right, end);
 if(result != -1){
 return result;
 }
 return finder(target, start, left); 
 }
}
 public int find(int target){
 // Set up the recursion for the binary search.
 return finder(target, 0, array.length - 1); 
 }
 public int get(int location){
 return array[location];
 }
 public static void main(String args[]){
 Scanner reader = new Scanner(System.in);
 int n, inv;
 n = reader.nextInt();
 inv = reader.nextInt();
 Bitonic BitonicArray = new Bitonic(n, inv);
 int targetLoc = reader.nextInt();
 int target = BitonicArray.get(targetLoc);
 System.out.printf("Value Queried: %d\n", target);
 int result = BitonicArray.find(target);
 if(result != -1) 
 System.out.printf("Found it at: %d, value at that location: %d", result, BitonicArray.get(result));
 else
 System.out.println("Not found.");
 }
}

Answer 1

• maxPossibleValue seems to be an instance-independent constant and should therefore be static and final (and, as such, should conventionally be in uppercase letters with words being separated by an underscore character, i.e. MAX_POSSIBLE_VALUE).

• array[i] = (int)Math.floor(Math.random() * maxPossibleValue);
  

  The problem with this line is that the array will never contain maxPossibleValue itself, because the value returned by Math.random() will always be less than, but never equal to 1.0. Besides, there is a simpler way of accomplishing what you want: Instead of using Math.random(), use an instance of Random:

  Random randomGenerator = new Random();
  for(int i = 0; i < n; i++){
   array[i] = randomGenerator.nextInt(maxPossibleValue + 1);
  }
  

• Your method of sorting the array doesn't work correctly. First of all, the integer at the index inv will never be modified, because your first sort only sorts the indexes 0 to inv - 1 and the second sort sorts the indexes inv + 1 to n - 1 (the end index passed to the sort method is exclusive).

  But even if you corrected this issue, the problem remains that you still don't know which of the two adjacent indices contains the greater integer. For example, when you have the array {1,2,3,4,5} and define 2 as the inversion point index (i.e. the third number in the array), and sort the first three numbers and the last two numbers separately, then you will get {1,2,3,5,4}, meaning the inversion point will be 3 instead of 2. If you really want to ensure that the number at the inversion point will be the largest number in the array, I don't think you will get around doing that manually, i.e. finding the largest number in the array and moving it to the inversion point by swapping it with the number previously there.

• The constructor Bitonic(int, int) does not check whether the passed arguments are valid. If it did, you would not need to use expressions like Math.min(inv + 1, n) when you sort the numbers on the right side of the inversion point (regardless of the fact that the sorting algorithm does not work correctly, as I previously pointed out).

• int currentPoint = (int)Math.floor(end + start)/2;
  

  There are several problems with this line. First, you probably forgot a pair of parentheses around the expression (end + start)/2. But even so, wrapping (end + start)/2 in Math.floor(double) is pointless, because (end + start)/2 already returns an integer (see here).

  Finally, you are risking an integer overflow with end + start. A way to prevent this would be to write start + (end - start)/2 instead (this is only guaranteed not to overflow if end >= start).

• This:

  if(currentValue < target){
   return finder(target, right, end);
  }
  else{
   int result = finder(target, start, left);
   if(result != -1){
   return result;
   }
   return finder(target, right, end);
  }
  

  can be written more concisely as:

  int result;
  if (currentValue >= target
   && (result = finder(target, start, left)) != -1) {
   return result;
  } else {
   return finder(target, right, end);
  }
  

  The same goes for the analogous code when currentValue lies after the inversion point.

Update

• Another thing just occurred to me: You can save unnecessary recursive calls if you changed the conditions of your two if blocks for being before and after the inversion point to allow one (but not both) of the two adjacent values to be equal to the current value. For example, if you are looking for the number 5 in the array {0,5,4,4,3,2,1}, and currentPoint == 3, so that leftValue == 4, currentValue == 4 and rightValue == 3, your program would enter the final else block and pointlessly search the numbers to the right of currentPoint.

  So instead, you could change the conditions to something like this:

  if(leftValue <= currentValue
   && currentValue <= rightValue
   && leftValue != rightValue)