public class MergeBinary {
// Merge sort
public static void mergeSort(int[] arr, int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}
// Merge two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
public static void merge(int[] arr, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int[] L = new int[n1];
int[] R = new int[n2];
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];
}
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++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Binary search
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
// find the middle index of the array
while (left <= right) {
int mid = left + (right - left) / 2;
// middle element of the array is the target return index
if (arr[mid] == target) {
return mid;
// if the middle element is greater than the target, search the left half of the array
} else if (arr[mid] < target) {
left = mid + 1;
// if the middle element is less than the target, search the right half of the array
} else {
right = mid - 1;
}
}
// target not found in the array
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 target
int index = binarySearch(arr, target);
if (index != -1) {
System.out.println("Index of " + target + " is " + index);
} else {
System.out.println(target + " not found in the array");
}
}
}
MergeBinary.main(null);