Binary Search Hack

• Binary Search Hack 1
• Binary Search Hack 2

Binary Search Hack 1

def binary_search(arr, low, high, target):
    """
    This function performs binary search recursively on a sorted integer array to find a target value.
    Args:
        arr: A sorted integer array.
        low: The lower index of the subarray being searched.
        high: The upper index of the subarray being searched.
        target: The integer value being searched for.
    Returns:
        The index of the target value if found, else -1.
    """
    # Check if the subarray has been exhausted
    if high >= low:
        # Calculate the middle index of the subarray
        mid = low + (high - low) // 2
        
        # If the target is found at the middle index, return it
        if arr[mid] == target:
            return mid
        
        # If the target is smaller than the middle element,
        # search the left half of the subarray
        elif arr[mid] > target:
            return binary_search(arr, low, mid - 1, target)
        
        # If the target is larger than the middle element,
        # search the right half of the subarray
        else:
            return binary_search(arr, mid + 1, high, target)
    else:
        # If the subarray has been exhausted and the target is not found, return -1
        return -1


# Test the function
arr = [1, 3, 5, 7, 9, 23, 45, 67]
target = 45
result = binary_search(arr, 0, len(arr)-1, target)
if result != -1:
    print(f"Element {target} is present at index {result}")
else:
    print(f"Element {target} is not present in the array")

Binary Search Hack 2

public static void mergeSort(int[] array) {
    if (array.length > 1) {
        int mid = array.length / 2;
        int[] leftArray = Arrays.copyOfRange(array, 0, mid);
        int[] rightArray = Arrays.copyOfRange(array, mid, array.length);

        mergeSort(leftArray);
        mergeSort(rightArray);

        int i = 0, j = 0, k = 0;
        while (i < leftArray.length && j < rightArray.length) {
            if (leftArray[i] < rightArray[j]) {
                array[k] = leftArray[i];
                i++;
            } else {
                array[k] = rightArray[j];
                j++;
            }
            k++;
        }
        while (i < leftArray.length) {
            array[k] = leftArray[i];
            i++;
            k++;
        }
        while (j < rightArray.length) {
            array[k] = rightArray[j];
            j++;
            k++;
        }
    }
}

public static int binarySearch(int[] array, int target) {
    int left = 0;
    int right = array.length - 1;

    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] == target) {
            return mid;
        } else if (array[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

public static void main(String[] args) {
    int[] array = {5, 6, 3, 1, 8, 9, 4, 7, 2};
    mergeSort(array);
    int index = binarySearch(array, 7);
    if (index != -1) {
        System.out.println("Index of 7 is: " + index);
    } else {
        System.out.println("7 is not found in the array");
    }
}