Advertisement
informaticage

binary search impl iter

May 22nd, 2021
1,446
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.35 KB | None | 0 0
  1. #include <stdbool.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <time.h>
  5.  
  6. #define LEN 16
  7.  
  8. bool binary_search(int v[], size_t length, int to_find);
  9.  
  10. int main(void) {
  11.   int vtest[LEN];
  12.   srand(time(NULL));
  13.   for (size_t i = 0; i < LEN; i++) {
  14.     vtest[i] = rand() % 30 + 1;
  15.   }
  16.  
  17.   // Simple sorting implementation
  18.   for (size_t i = 0; i < LEN; i++) {
  19.     for (size_t j = i + 1; j < LEN; j++) {
  20.       if (vtest[i] > vtest[j]) {
  21.         int temp = vtest[i];
  22.         vtest[i] = vtest[j];
  23.         vtest[j] = temp;
  24.       }
  25.     }
  26.   }
  27.  
  28.   // Printing the resulting array
  29.   printf("[ ");
  30.   for (size_t i = 0; i < LEN; i++) {
  31.     printf("%d ", vtest[i]);
  32.   }
  33.   printf("]\n");
  34.  
  35.   // Asking the element to be searched for
  36.   int to_find;
  37.   printf("Insert to find: ");
  38.   scanf("%d", &to_find);
  39.  
  40.   // Calling binary search for the result
  41.   printf("Found: %s", binary_search(vtest, LEN, to_find) ? "true" : "false");
  42.   return 0;
  43. }
  44.  
  45. // Loop implementation
  46. bool binary_search(int v[], size_t length, int to_find) {
  47.   size_t i = 0, j = length;
  48.  
  49.   while (j - i > 1) {
  50.     // (i + j) / 2
  51.     size_t mid = (i + (j - i) / 2);
  52.  
  53.     if (v[mid] < to_find)
  54.       i = mid;
  55.     if (v[mid] > to_find)
  56.       j = mid;
  57.     if (v[mid] == to_find)
  58.       return true;
  59.   }
  60.  
  61.   printf("i: %d, j: %d\n", i, j);
  62.   return v[i] == to_find || v[j] == to_find;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement