Question

1. Modify the binary search algorithm implemented in the search method of the HighArray class, to print a trace showing for each iteration of the search, the upper and lower limits of the search and the middle item selected in the binary split.
   
   The output might look something like this:
   
   Pass 1 left=0 right=9 pivot=4
   Pass 2 left=0 right =3 pivot =1
   Pass 3 left=2 right =3 pivot =2

Answer 1

Solution:

Program implementation:

public class HighArray {
// binary_search() method takes two parameters.
int binary_search(int array[], int target)
{
int left= 0,i=1; // variable left stores the first index and i variable is initialised to 1 to use for passes.
int right = array.length - 1; // variable right is initialised to right most index of the array.
while (left <= right) {
System.out.print("Pass "+(i++));// prints the passes.
int pivot = left + (right - left) / 2; // calculates the pivot index.
// prints the left, right and pivot value.
System.out.println(" left= "+left+" "+"right= "+right+" "+"pivot="+pivot);
if (array[pivot] == target) // if value present at pivot is target value.
return pivot;
// if value present at pivot is less than target.
if (array[pivot] < target)
left = pivot + 1;
// if value present at pivot is greater than target.
else
right = pivot - 1;
}
// if value is not present in the array.
return -1;
}

public static void main(String args[])
{
HighArray obj = new HighArray(); // creates an object of class HighArray.
// creates an array and populates the array with ordered data.
int array[] = { 1, 2, 3, 4, 6, 20, 40, 56, 89, 98, 108, 129, 134 };
int target = 134; // target variable stores the target to search.
int n = array.length; // variable n stores the length of the array.
// function call to binary_search().
int res = obj.binary_search(array,target);
if (res == -1)
System.out.println("Target not found");
else
System.out.println("Target found at "+ "pivot " + res);
}
}

Program screenshot:

Program output screenshot: