C   32

binary-search.c

Guest on 15th January 2022 09:22:37 AM

  1. #include<stdio.h>
  2. #define SIZE 1000000
  3.  
  4. void print_array(int a[], int);
  5. int bsearch(int a[], unsigned int beg, unsigned int end, int val);
  6.  
  7. void main() {
  8.   int A[SIZE], i;
  9.   int pos = rand() % SIZE;
  10.   printf("pos is %d\n", pos);
  11.   A[pos] = 17;
  12.   for (i = 1; (pos + i) < SIZE; i++)
  13.     A[pos+i] = 17 + i;
  14.   for (i = 1; (pos - i) >= 0; i++)
  15.     A[pos-i] = 17 - i;
  16.   pos = bsearch(A, 0, SIZE-1, 17);
  17.   if (pos > -1)
  18.     printf("17 occurs at position %d\n", pos);
  19.   else
  20.     printf("17 does not occur\n");
  21. }
  22.  
  23. int bsearch(int a[], unsigned int beg, unsigned int end, int val) {
  24.   int mid;
  25.   if (beg == end)
  26.     if (a[beg] == val)
  27.       return beg;
  28.     else
  29.       return -1;
  30.   mid = (beg + end) / 2;
  31.   if (val <= a[mid])
  32.     return bsearch(a, beg, mid, val);
  33.   else
  34.     return bsearch(a, mid+1, end, val);
  35. }
  36.  
  37. void print_array(int a[], int len) {
  38.   int i;
  39.   for (i = 0; i < len; i++)
  40.     printf("%d ", a[i]);
  41.   printf("\n");
  42. }

Raw Paste


Login or Register to edit or fork this paste. It's free.