Binary search using quick sort

Algorithm

Copy
swap(arr, i, j)
Begin
	Set temp = arr[i]
	Set arr[i] = arr[j]
	Set arr[j] = temp
End

Copy
partition(arr, low, mid)
Begin
	Set pivot = arr[low]
	Set i = low
	Set j = high
	while (i < j), do
		while (i < high && arr[i] <= pivot), do
			Increment i by 1
		End While 
		while (j > low && arr[j] > pivot), do
			Decrement j by 1
		End While
		if (i < j), then
			Call swap(arr, i, j)
		End If
	End While
	Call swap(arr, low, j)
	return j
End

Copy
quicksort(arr, low, high)
Begin
	if (low >= high) return
	Set pivot = partition( arr, low, high)
	Call quicksort(arr, low, pivot - 1)
	Call quicksort(arr, pivot + 1, 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 quicksort(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 swap(int *arr, int i, int j) {
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

int partition(int *arr, int low, int high) {
  int pivot = arr[low];
  int i = low;
  int j = high;

  while (i < j) {
    while (i < high && arr[i] <= pivot) i++;
    while (j > low && arr[j] > pivot) j--;
    if (i < j) swap(arr, i, j);
  }

  swap(arr, low, j);
  return j;
}

void quickSort(int *arr, int low, int high) {
  if (low >= high) return;
  int pivot = partition(arr, low, high);
  quickSort(arr, low, pivot - 1);
  quickSort(arr, pivot + 1, high);
}

int binarySearch(int *arr, int size, int elem) {
  int low = 0;
  int high = size - 1;

  while (low <= high) {
    int mid = low + (high - low) / 2;
    if (arr[mid] > elem) high = mid - 1;
    else if (arr[mid] < elem) low = mid + 1;
    else return mid;
  }

  return -1;
}

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);

  quickSort(arr, 0, size - 1);

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

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

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