Binary Search Hack 2
Here is my merge sort hack.
public class BinarySearch {
// Merge sort algorithm
public static void mergeSort(int[] arr, int l, int r) {
if (l < r) {
// Calculate the middle index
int m = l + (r - l) / 2;
// Recursively sort the left and right halves
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}
// Merge two sorted sub-arrays
public static void merge(int[] arr, int l, int m, int r) {
// Calculate the sizes of the two sub-arrays
int n1 = m - l + 1;
int n2 = r - m;
// Create temporary arrays to hold the two sub-arrays
int[] L = new int[n1];
int[] R = new int[n2];
// Copy data into the temporary arrays
for (int i = 0; i < n1; ++i) {
L[i] = arr[l + i];
}
for (int j = 0; j < n2; ++j) {
R[j] = arr[m + 1 + j];
}
// Merge the two sub-arrays into the original array
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy any remaining elements from the left sub-array
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy any remaining elements from the right sub-array
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Binary search algorithm
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
// Continue searching while the left and right indices don't cross
while (left <= right) {
// Calculate the middle index
int mid = left + (right - left) / 2;
// If the target is found at the middle index, return it
if (arr[mid] == target) {
return mid;
// If the middle element is greater than the target, search the left half
} else if (arr[mid] > target) {
right = mid - 1;
// If the middle element is less than the target, search the right half
} else {
left = mid + 1;
}
}
// Target not found
return -1;
}
public static void main(String[] args) {
int[] arr = {5, 6, 3, 1, 8, 9, 4, 7, 2};
int target = 7;
// Sort the array using merge sort
mergeSort(arr, 0, arr.length - 1);
// Perform binary search to find the index of the target
int index = binarySearch(arr, target);
// Print the result
if (index != -1) {
System.out.println("Index of " + target + " is " + index);
} else {
System.out.println(target + " not found in the array");
}
}
}
BinarySearch.main(null);