Question

Assume you need to write a Java program that uses a binary search algorithm to search a sorted array for a given value.

1. Write a Java pseudocode that uses recursion to accomplish the task. Here is a hint. When you are searching for a particular value in an array, there are two possible outcomes. 1) The value is found and the array index of that value is returned. 2) The value is not found and we return -1. (5 points).

2. Convert the pseudocode in 1 above into a working Java program. Submit the program separately as a java file with the file name MyBinarySearch (6 points).

3. Refer to Figure 3.2 in page 33 of the textbook. What type of process flow would you use when writing the software in parts 1 and 2 above? Justify your answer in at least two sentences. (4 points).

Answer 1

Thanks for the question.
Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks
===========================================================================



In Binary Search we basically ignore half of the elements just after one comparison.

        Compare num with the middle element.
        If num matches with middle element, we return the mid index.
        Else If num is greater than the mid element, then num  can only lie in right half sub array after the mid element. So we recur for right half.
        Else (num  is smaller) recur for the left half.

============================================================================================

// Java implementation of recursive Binary Search
public class BinarySearch {
    // Returns index of num if it is present in arr[l..r], else
    // return -1
    int binarySearch(int arr[], int low, int upper, int num) {
        if (upper >= low) {
            int mid = low + (upper - low) / 2;

            // If the element is present at the middle itself
            if (arr[mid] == num)
                return mid;

            // If element is smaller than mid, then it can only
            // be present in left subarray
            if (arr[mid] > num)
                return binarySearch(arr, low, mid - 1, num);

            // Else the element can only be present in right
            // subarray
            return binarySearch(arr, mid + 1, upper, num);
        }

        // We reach here when element is not present in array
        return -1;
    }

    // Driver method to test above
    public static void main(String args[]) {
        BinarySearch binSearch = new BinarySearch();
        int arr[] = {21, 33, 37, 40, 80, 99, 101, 140, 410};
        int n = arr.length;
        int num = 101;
        int result = binSearch.binarySearch(arr, 0, n - 1, num);
        if (result == -1)
            System.out.println("Element not present");
        else
            System.out.println("Element found at index " + result);
    }
}

======================================================================================