Question

Task 3 Java 8 You are given an implementation of a function: class Solution { public int solution(int[] a, int x); }

This function, when given an array A of N integers, sorted in non- decreasing order, and some integer X, looks for X in A. If X is present in A, then the function returns position of (some) occurrence of Xin A. Otherwise, the function returns -1. For example, given the following array: A[0] = 1 A[1] = 2 A[2] = 5 A[3] = 9 A[4] = 9 and X = 5, the function should return 2, as A[2] = 5. The attached code is still incorrect for some inputs. Despite the error(s), the code may produce a correct answer for the example test cases. The goal of the exercise is to find and fix the bug(s) in the implementation. You can modify at most three lines. Assume that: • Nis an integer within the range [0..100,000); • each element of array A is an integer within the range (-2,000,000,000..2,000,000,000): • array A is sorted in non-decreasing order, • X is an integer within the range (-2,000,000,000..2,000,000,000).

Answer 1

The student's Java 8 function is intended for a binary search within a sorted array. The solution includes the corrected implementation of the binary search, paying particular attention to the calculation of the middle index and adjusting the search boundaries correctly.

Step-by-step explanation:

The student is attempting to fix a bug in a Java 8 function that performs a binary search. Since the array A is sorted in non-decreasing order, a binary search algorithm can efficiently find the index of an element X. If the element X is found, the index is returned; otherwise, -1 is returned. The optimal solution involves verifying that the binary search correctly handles the boundaries of the search space and mid-calculation.

Here is a corrected binary search implementation

public int solution(int[] a, int x) {
int left = 0;
int right = a.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // to prevent potential overflow

if (a[mid] == x) {
return mid;
} else if (a[mid] < x) {
left = mid + 1;
} else {
right = mid - 1;
}
}

return -1;
}

The primary issues usually involve the calculation of the middle index to ensure no overflow occurs and that the algorithm correctly changes the boundaries of the search space (left and right variables).