main.cpp

00001 #include<stdio.h>
00002 #include "mbed.h"
00003 #include "Serial.h"
00004 Serial uart1(USBTX,USBRX); 
00005 /* Function to find the cross over point (the point before
00006    which elements are smaller than or equal to x and after
00007    which greater than x)*/
00008 int findCrossOver(int arr[], int low, int high, int x)
00009 {
00010     // Base cases
00011   if (arr[high] <= x) // x is greater than all
00012     return high;
00013   if (arr[low] > x)  // x is smaller than all
00014     return low;
00015     
00016   // Find the middle point
00017   int mid = (low + high)/2;  /* low + (high - low)/2 */
00018  
00019   /* If x is same as middle element, then return mid */
00020   if (arr[mid] <= x && arr[mid+1] > x)
00021     return mid;
00022  
00023   /* If x is greater than arr[mid], then either arr[mid + 1]
00024     is ceiling of x or ceiling lies in arr[mid+1...high] */
00025   if(arr[mid] < x)
00026       return findCrossOver(arr, mid+1, high, x);
00027  
00028   return findCrossOver(arr, low, mid - 1, x); 
00029 }  
00030 
00031 // This function prints k closest elements to x in arr[].
00032 // n is the number of elements in arr[]
00033 void printKclosest(int arr[], int x, int k, int n)
00034 {
00035     // Find the crossover point
00036     int l = findCrossOver(arr, 0, n-1, x);
00037     int r = l+1;   // Right index to search
00038     int count = 0; // To keep track of count of elements already printed
00039  
00040     // If x is present in arr[], then reduce left index
00041     // Assumption: all elements in arr[] are distinct
00042     if (arr[l] == x) l--;
00043  
00044     // Compare elements on left and right of crossover
00045     // point to find the k closest elements
00046     while (l >= 0 && r < n && count < k)
00047     {
00048         if (x - arr[l] < arr[r] - x)
00049             uart1.printf("%d ", arr[l--]);
00050         else
00051             uart1.printf("%d ", arr[r++]);
00052         count++;
00053     }
00054  
00055     // If there are no more elements on right side, then
00056     // print left elements
00057     while (count < k && l >= 0)
00058         uart1.printf("%d ", arr[l--]), count++;
00059  
00060     // If there are no more elements on left side, then
00061     // print right elements
00062     while (count < k && r < n)
00063         uart1.printf("%d ", arr[r++]), count++;
00064 }
00065 
00066 /* Driver program to check above functions */
00067 int main()
00068 {
00069    uart1.baud(9600);
00070    wait(0.1);
00071    int arr[] ={12, 16, 22, 30, 35, 39, 42,
00072                45, 48, 50, 53, 55, 56};
00073    int n = sizeof(arr)/sizeof(arr[0]);
00074    int x = 35, k = 4;
00075    printKclosest(arr, x, 4, n);
00076    while(1)
00077    {
00078        wait(0.1);
00079        uart1.printf("%d \n",printKclosest);
00080    }
00081    //return 0;
00082 }