Question

3. Write the function find sorted elt whose input is a vector sorted in increasing order and an element

x. The output is 0 if the element x does not occur in v, 1 if the element x does occur in v. Below is the

algorithm you should implement, known as the binary search algorithm. Note that the code below

returns the index, but we want to return true or false, not the index, so adjust your code accordingly.

Algorithm. Given an array A of n elements with values or records A1, . . . , An and target value T, the

following subroutine uses binary search to find the index T in A.

(a) Set L to 1 and R to n.

(b) If L > R, the search terminates as unsuccessful. Set m (the position of the middle element) to

the floor of (L + R)/2.

(c) If Am < T, set L to m + 1 and go to step 2.

(d) If Am > T, set R to m − 1 and go to step 2.

(e) If Am = T, the search is done; return m.

Comparing an element of v to x (either with == or with <) counts as one step. Setting the output

value, setting the value of n, setting the value of i, all also count as one step.

(a) How many steps does it take for the input of v=[2, 5, 6, 7, 9, 10, 11, 12] and x = 7? List each step in order.

(b) Give an example of an unsorted vector v and an element x in v for which the algorithm would

return an answer of 0.

(c) What’s the most number of steps it could take for a length 8 input?

(d) Estimate the most number of steps it could take for a length 1000 input? Explain.

Answer 1

Here is the code implementing binary search.

public class BinarySearch{
    private static int arrayCheckSortedOrNot(int [] array){
        int flag = 1;
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i] > array[i + 1]) {
                flag = 0;
                break;
            }
        }
        return flag;
    }
    static int binarySearch(int [] values, int n, int target)
    {
        int R = n;
        int L = 1;
        int midIndx;  // Index of middle element
        int stepCount = 0;  // Steps taken
        if ( L > R){
            System.out.println("The search terminates as unsuccessful");
            System.exit(0);
        }
        while(R >= L)
        {
            midIndx = (L + R) / 2;
            stepCount++;
            System.out.println("The step required to search : " + stepCount);
            if (values[midIndx] <  target){
                L = (midIndx + 1);
            }else if (values[midIndx] >  target){
                R = (midIndx - 1);
            }else{
               return midIndx;
            }
        }
        return -1; // When search element not found in the array
    }

    public static boolean resultFinal(int [] values, int n, int target){
        // This method for returning int value
        int result = binarySearch(values, n, target);
        if(result == -1)
        {
            return false;
        }else {
            return true;
        }
    }
    
    public static void main(String [] args){ // Here is where you start the main call
        int [] values = {2, 5, 6, 7, 9, 10, 11, 12};
        int n = values.length;
        int target = 7;
        int checkForUnsortedArray = arrayCheckSortedOrNot(values);
        if (checkForUnsortedArray==0){
            System.out.println(checkForUnsortedArray); // Display 0 as the array is unsorted
        }else {
            resultFinal(values, n, target); //else enter binay search method
        }
    }
}

(a) How many steps does it take for the input of v=[2, 5, 6, 7, 9, 10, 11, 12] and x = 7? List each step in order.

O/P :

The step required to search : 1
The step required to search : 2
The step required to search : 3

(b) Give an example of an unsorted vector v and an element x in v for which the algorithm would return an answer of 0.

Yes the code does return 0 for an unsorted array - Tested with {92, 5, 600, 7, 9, 10, 11, 12} - returned 0

(c) What’s the most number of steps it could take for a length 8 input?

Max number of steps would be 3 as the array will be divided into 2 halves.

(d) Estimate the most number of steps it could take for a length 1000 input? Explain.

It would approximately take log2(1000). More number of steps are taken when you are trying to search for an item which is not present in the array, or trying to find the left extreme or the right extreme items.