Minimum Common Value

class Solution {
public:
    int findShared(vector<int>& arr1, vector<int>& arr2) {
        if (arr1.size() > arr2.size()) {
            return findShared(arr2, arr1);
        }

        for (int element : arr1) {
            if (performBinarySearch(element, arr2)) {
                return element;
            }
        }

        return -1;
    }

private:
    bool performBinarySearch(int key, vector<int>& data) {
        int low = 0;
        int high = data.size() - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (data[mid] > key) {
                high = mid - 1;
            } else if (data[mid] < key) {
                low = mid + 1;
            } else {
                return true;
            }
        }
        return false;
    }
};

This C++ solution identifies the minimum common value between two sorted integer arrays. It employs the binary search technique to effectively find a shared element with the least value that exists in both arrays. If no common element is found, the function returns -1.

Here’s a breakdown of working:

• Initialize a function, findShared, that compares two integer vectors.
• If the first array is larger than the second one, the function calls itself with the arrays reversed to optimize search performance, using the smaller array for the outer loop.
• The function iterates through elements of the smaller array (arr1) and uses a helper function performBinarySearch to check if each element is present in the second array (arr2).
• If performBinarySearch finds the element, it immediately returns that element as the result, ensuring it's the smallest possible, given the sorted order of arrays.
• The performBinarySearch function checks the presence of a given key in the data array, implementing the classic binary search algorithm:
  • Calculate the middle of the current search segment.
  • If the middle element is greater than the key, narrow the search to the lower segment.
  • If it's lower, shift to the upper segment.
  • If it matches the key, return true indicating the key is found.
  • If no match is found across the entire segment, return false.
• If no common element is found after exhausting all elements of the smaller array, the function returns -1.

This method efficiently finds the smallest common value due to the sorted nature of input arrays and the logarithmic complexity of the binary search operation. Moreover, it ensures that even if one array is significantly larger than the other, the performance remains optimized by always iterating through the smaller array.

public class Solution {
    public int findFirstCommon(int[] set1, int[] set2) {
        if (set1.length > set2.length) {
            return findFirstCommon(set2, set1);
        }
        
        for (int value : set1) {
            if (indexOfElement(value, set2)) {
                return value;
            }
        }

        return -1;
    }

    private boolean indexOfElement(int targetValue, int[] data) {
        int start = 0;
        int end = data.length - 1;
        while (start <= end) {
            int middle = start + (end - start) / 2;
            if (data[middle] > targetValue) {
                end = middle - 1;
            } else if (data[middle] < targetValue) {
                start = middle + 1;
            } else {
                return true;
            }
        }
        return false;
    }
}

The Java solution provided searches for the first common element between two integer arrays. The solution consists of the main public method, findFirstCommon, and a helper private method, indexOfElement.

• The findFirstCommon method begins by ensuring the smaller of the two arrays is always the first array to be iterated upon. This optimization reduces the total number of comparisons required.
• It iterates through each element of the smaller array (referred to as set1) and uses the indexOfElement method to check if the current element exists in the second array (set2). If a common value is found, it immediately returns this value.
• If no common elements are found after checking all values in the smaller array, the method returns -1, indicating no commonality.

The indexOfElement method implements a binary search algorithm:

• The method takes a targetValue and an array data as parameters. It aims to find if the targetValue is present in the data array using binary search.
• It initializes two pointers, start and end, to represent the range of indices in the array currently being searched.
• Within a loop, it calculates the middle index and compares the value at this index to the targetValue. Depending on the comparison result, it adjusts the start or end pointers to either half of the array and continues searching.
• If the middle value equals the targetValue, it returns true. If the search concludes without finding the target, it returns false.

Overall, this solution leverages efficient searching techniques to minimize the operations needed to find a common value, making it suitable for large datasets or performance-sensitive applications. The choice of binary search particularly boosts efficiency given that one of the arrays can be iteratively scanned with logarithmic time complexity for each lookup.

class Solution:
    def findFirstCommonElement(self, list1: List[int], list2: List[int]) -> int:

        def search_element(target, dataList):
            low = 0
            high = len(dataList) - 1
            while low <= high:
                mid = low + (high - low) // 2
                if dataList[mid] > target:
                    high = mid - 1
                elif dataList[mid] < target:
                    low = mid + 1
                else:
                    return True
            return False

        # Swap lists to optimize the search by using binary search on the larger list
        if len(list1) > len(list2):
            return self.findFirstCommonElement(list2, list1)

        # Loop through the smaller list and search each element in the larger list
        # Return the first match found
        for element in list1:
            if search_element(element, list2):
                return element

        # If no common elements are found, return -1
        return -1

The Python program provided defines a method to find the first common element between two lists, utilizing binary search for efficient lookup. Here's a quick guide on how the code tackles the problem:

• Define Search Function: Inner function search_element implements binary search. This function takes a target value and a dataList where it attempts to find the target. If the target is present, it returns True, otherwise False.

• Optimize By List Size: Prior to searching, the function checks the sizes of list1 and list2 and swaps them if list1 is larger. This optimization helps reduce the number of binary searches by always performing the search on the larger list.

• Search for Common Element: The smaller list (list1 after a possible swap) is iterated over, and each element is searched in the larger list (list2). The first element found in both lists is immediately returned.

• No Common Elements: If no elements are common between the two lists even after checking each element of the smaller list, the function returns -1.

This approach ensures that the search is as efficient as possible by minimizing the number of binary search operations required to find the first common element. The choice of binary search over a linear search is crucial for handling large lists, significantly speeding up the process in such cases.