Binary search using merge sort

Algorithm

Copy
merge(arr, low, mid, high)
Begin
	Declare i = low
	Declare j = mid + 1
	Declare k = 0
	Declare newArr[high - low + 1];
	
	while (i <= mid && j <= high), do
		if (arr[i] <= arr[j]), then
			Set newArr[k] = arr[i];
			Increment i by 1
			Increment k by 1
		else 
			Set newArr[k] = arr[j]
			Increment j by 1
			Increment k by 1
		End If
	End While
	
	while (i <= mid), do
		Set newArr[k] = arr[i]
		Increment k by 1
		Increment i by 1
	End While
	
	while (j <= high), do
		Set newArr[k] = arr[j]
		Increment k by 1
		Increment j by 1
	End While
	
	for (i = 0; i < k; i++), do
		Set arr[low + i] = newArr[i]
	End For
End

Copy
mergesort(arr, low, high)
Begin
	if (low >= high) return
	Set mid = low + (high - low) / 2
	Call mergesort(arr, low, mid)
	Call mergesort(arr, mid + 1, high)
	Call merge(arr, low, mid, high)
End

Copy
binarySearch(arr, size, elem)
Begin
	Declare start = 0
	Declare stop = size - 1
	Declare index = -1
	while (start  <= stop), do
		Set mid = start + (stop - start) / 2
		if (arr[mid] < elem), then
			Set start = mid + 1
		else if (arr[mid] > elem), then
			Set stop  = mid - 1
		else 
			Set index = mid
			break
		End If
	End While
	return index
End

Copy
main() 
Begin
	Read array size, "size"
	Declare arr[size]
	for (i = 0; i < size; i++), do
		Read element store in arr[i]
	End For
	Read element to search, "elem"
	Call mergesort(arr, 0, size - 1)
	Display sorted array "arr"
	Set index = binarySearch(arr, size, elem)
	if (index == -1),  then
		Display "Element not found"
	else 
		Display "Element found at position " + (index + 1)
	End If
End

Program

Copy
#include <stdio.h>

void merge(int *arr, int low, int mid, int high) {
  int i = low;
  int j = mid + 1;
  
  int k = 0;
  int newArr[high - low + 1];

  while (i <= mid && j <= high) {
    if (arr[i] <= arr[j]) newArr[k++] = arr[i++];
    else newArr[k++] = arr[j++];
  }

  while (i <= mid) newArr[k++] = arr[i++];
  while (j <= high) newArr[k++] = arr[j++];

  for (int i = 0; i < k; i++)
    arr[low + i] = newArr[i];
}

void mergeSort(int *arr, int low, int high) {
  if (low >= high) return;
  int mid = low + (high - low) / 2;
  mergeSort(arr, low, mid);
  mergeSort(arr, mid + 1, high);
  merge(arr, low, mid, high);
}

int binarySearch(int *arr, int size, int elem) {
  int start = 0;
  int stop = size - 1;
  int index = -1;

  while (start <= stop) {
    int mid = start + (stop - start) / 2;
    if (arr[mid] > elem) {
      stop = mid - 1;
    } else if (arr[mid] < elem) {
      start = mid + 1;
    } else {
      index = mid;
      break;
    }
  }

  return index;
}

int main() {
  int size, elem;
  printf("Enter array size: ");
  scanf("%d", &size);

  int arr[size];
  printf("Enter array elements: ");
  for (int i = 0; i < size; i++)
    scanf("%d", &arr[i]);
  
  printf("Enter element to search: ");
  scanf("%d", &elem);

  mergeSort(arr, 0, size - 1);

  printf("Sorted Array: ");
  for (int i = 0; i < size; i++) 
    printf("%d ", arr[i]);

  int index = binarySearch(arr, size, elem);

  if (index == -1) printf("\n\nElement not found\n");
  else printf("\n\nElement found at position %d\n", (index + 1));
}