#include <stdio.h>
#include <stdlib.h>
#include<time.h>

#define MAX 100

int list[MAX];

void display() {
   int i;
   //printf("[");
   srand(time(0));	
   // navigate through all items 
   for(i = 0; i < MAX; i++) {
      list[i]=rand();
	  printf("%10d\n",list[i]);
	  if(i%20==0)
	  {
	  	getchar();
	  	system("cls");
	  }
   }
	
   //printf("]\n");
}

void print()
{
	int i;
	for(i = 0; i < MAX; i++) {
	  printf("%10d\n",list[i]);
   }
}


void bubbleSort() {
   int temp;
   int i,j;
	
   int swapped = 0;
   
   display();
   
   // loop through all numbers 
   for(i = 0; i < MAX-1; i++) { 
      swapped = 0;
		
      // loop through numbers falling ahead 
      for(j = 0; j < MAX-1-i; j++) {
         printf("     Items compared: [ %d, %d ] ", list[j],list[j+1]);

         // check if next number is lesser than current no
         //   swap the numbers. 
         //  (Bubble up the highest number)
			
         if(list[j] > list[j+1]) {
            temp = list[j];
            list[j] = list[j+1];
            list[j+1] = temp;

            swapped = 1;
            printf(" => swapped [%d, %d]\n",list[j],list[j+1]);
         } else {
            printf(" => not swapped\n");
         }
			
      }

      // if no number was swapped that means 
      //   array is sorted now, break the loop. 
      if(!swapped) {
         break;
      }
      
      printf("Iteration %d#: ",(i+1)); 
   }
   print();
}

int binarySearch(int l, int r, int x,int *times)//list[100] 
{ 
   if (r >= l) 
   { 
        int mid = l + (r - l)/2; 
        printf("\nbinarySearch---mid=%3d",mid);
        getchar();
        // If the element is present at the middle  
        // itself 
        if (list[mid] == x)
		{   
            printf("\nfound at position:%3d after:%3d iterations...",mid,*times);
			return mid;
		}
  
        // If element is smaller than mid, then  
        // it can only be present in left subarray 
        if (list[mid] > x)  
        {
        	printf("\nbinary:1...");
        	getchar();
        	//(*times)++;
        	*times=(*times)+1;
        	printf("\nx less than middle--->*times=%d",*times);
        	getchar();
            return binarySearch(l, mid-1, x,times); 
        }
        // Else the element can only be present 
        // in right subarray 
        else{
        	printf("\nbinary:2...");
        	getchar();
		//(*times)++;
		*times=(*times)+1;
		printf("\nx greater than middle--->*times=%d",*times);
		getchar();
		return binarySearch(mid+1, r, x,times);
		}
   } 
  
   // We reach here when element is not  
   // present in array 
   printf("number of iterations:%3d \n",*times);
   return -1; 
}