C Program to Implement Binary Search with Window

This C program implements Binary search with window.

Here is the source code of the C program Implement a binary search algorithm such that search starts from the pth element and searches subsequently with a jump of 2^i i.e. p+1,p+2,p+4,p+8,…and continues until the correct window for the key is obtained. Now binary search is implemented in this window.. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C program to implement Binary search with window
  3.  */
  4. #include <stdio.h>
  5.  
  6. /*  Function for Binary search  */
  7. void binary_search(int array[], int first, int last, int n)
  8. {
  9.     int i ,middle;
  10.     middle = (first + last) / 2;
  11.  
  12.     while (first <= last) {
  13.     if (array[middle] < n)
  14.         first = middle + 1;
  15.     else if (array[middle] == n) {
  16.         printf("%d found at location %d.\n", n, middle+1);
  17.         break;
  18.     }
  19.     else
  20.         last = middle - 1;
  21.  
  22.     middle = (first + last) / 2;
  23.     }
  24.     if ( first > last )
  25.     printf("Not found! %d is not present in the list.\n", n);
  26. }
  27. /*  End of binary_search()  */
  28.  
  29. /*  Function to search for the window */
  30. search(int arr[], int size, int data)
  31. {
  32.     int p = (size - 1) / 2, low, high, a1 = 0, a2 = 1, i = 1;
  33.     low = p + a1;
  34.     high = p + a2;
  35.     while(i)
  36.     {
  37.     if(data >= arr[low] && data <= arr[high])
  38.     {
  39.         binary_search(arr, low, high, data);
  40.         break;
  41.     }
  42.     else if(data < arr[low])
  43.     {
  44.         binary_search(arr, 0, low, data);
  45.         break;
  46.     }
  47.     else
  48.     {
  49.         a2 = a2 * 2;
  50.         low = high;
  51.         high = p + a2;
  52.     }
  53.     }
  54. }
  55. /*  End of search()  */
  56.  
  57. /*  The main() begins  */
  58. int main()
  59.  
  60. {
  61.     int a[200], i, j, n, size;
  62.     printf("Enter the size of the list:");
  63.     scanf("%d", &size);
  64.     printf("Enter %d Integers in ascending order\n", size);
  65.     for (i = 0; i < size; i++)
  66.     scanf("%d", &a[i]);
  67.     printf("Enter value to find\n");
  68.     scanf("%d", &n);
  69.     search(a, size, n );
  70.     return 0;
  71. }

$ gcc Binarysearch_new.c
$ ./a.out
Enter the size of the list:10
Enter 10 Integers in ascending order
1 2 3 4 5 6 7 8 9 10
Enter value to find
7
7 found at location 7.

Sanfoundry Global Education & Learning Series – 1000 C Algorithms.

advertisement
advertisement
If you wish to look at all C Algorithms and Solutions, go to C Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.