Implement recursive binary sort.

/*
Name:
Copyright: Deitel C How to Program
Author: StackOverflow1453
Date: 6/21/2013 7:02:52 PM
Description:

(Binary Search) Modify the program of Fig. 6.19 to use a recursive binarySearch function to perform the binary search
of the array. The function should receive an integer array and the starting subscript and ending subscript as arguments. If the search
key is found, return the array subscript; otherwise, return –1.
*/

#include <stdio.h>
#define SIZE 20
int binarySortRecursive(int key, int low, int high);
void printSubArray(int b[],int low, int high);
int myArray[SIZE]={0};
int i, middle;

int main(void) {

	int key;
	//intialize array sorted
	for (i = 0; i < SIZE; i++)
	{
		myArray[i]=i*2;

	}
	printf("Enter a number between 0 and 38: ");
	scanf("%d",&key);

	if(binarySortRecursive(key, 0, SIZE-1)){

		printf("Key is found at index %d", middle);

	}
	else
	{
		printf("key is not found");
	}

	getch();

}
//recursive BinarySort algorithm
int binarySortRecursive(int key, int low, int high){

	printSubArray(myArray,low,high);
	middle=(low+high)/2;

	if (myArray[middle]==key)
	{
		return 1;
	}
	else if (key<myArray[middle] && low<high) //lower portion
	{  		
		return binarySortRecursive(key, low, middle-1);
	}
	else if(key>myArray[middle] && low<high)
	{   		
		return binarySortRecursive(key, middle+1, high);
	}
	else
	{
		return 0;
	}
}
//prints new SubArray
void printSubArray(int b[], int m, int n){

	for (i = m; i <= n; i++)
	{
		printf("%d ",myArray[i]);
	}
	printf("\n");
}
About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s