Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * C Program to Perform Binary Search using Recursion
- */
- #include <stdio.h>
- #include <stdlib.h>
- void binary_search(int [], int, int, int);
- void quicksort (int [], int, int);
- int main()
- {
- int key, size, i;
- int list[50];
- printf("Enter size of a list: ");
- scanf("%d", &size);
- printf("Generating random numbers\n");
- for(i = 0; i < size; i++)
- {
- list[i] = rand() % 100;
- printf("%d ", list[i]);
- }
- quicksort(list, 0, size - 1);
- printf("\n\nSorted random numbers\n");
- for(i = 0; i < size; i++)
- {
- printf("%d ", list[i]);
- }
- printf("\n\nEnter key to search\n");
- scanf("%d", &key);
- binary_search(list, 0, size, key);
- }
- void quicksort(int list[], int low, int high)
- {
- int pivot, i, j, temp;
- if (low < high)
- {
- pivot = low;
- i = low;
- j = high;
- while (i < j)
- {
- while (list[i] <= list[pivot] && i <= high)
- {
- i++;
- }
- while (list[j] > list[pivot] && j >= low)
- {
- j--;
- }
- if (i < j)
- {
- temp = list[i];
- list[i] = list[j];
- list[j] = temp;
- }
- }
- temp = list[j];
- list[j] = list[pivot];
- list[pivot] = temp;
- quicksort(list, low, j - 1);
- quicksort(list, j + 1, high);
- }
- }
- void binary_search(int list[], int lo, int hi, int key)
- {
- int mid;
- if (lo > hi)
- {
- printf("Key not found\n");
- return;
- }
- mid = (lo + hi) / 2;
- if (list[mid] == key)
- {
- printf("Key found\n");
- }
- else if (list[mid] > key)
- {
- binary_search(list, lo, mid - 1, key);
- }
- else if (list[mid] < key)
- {
- binary_search(list, mid + 1, hi, key);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment