/* This is a sample program for Labtest I Problem 1 */ 

#include<stdio.h>
#define MAX 100


int main(void) {
	int i, j, t, array[MAX], n, x, z, low, high, mid, flag=0;
	int compare_sort=0, compare_binsearch=0, compare_sum=0;
	int expect; 

	/* Take the input size of the array*/ 
	printf("\n What is the size of the array (it should be less than %d)::> ",MAX);
	scanf("%d", &n);

	/* Take the input to the array */
	for(i=0;i<n;i++) {
		printf("\n Enter the %d-th element::> ",i+1);
		scanf("%d",&array[i]);
	} 

	/* We use bubble sort to do the sorting. There are other 
	better methods to sort an array. We will learn them later.
	The logic for bubble sort -- The maximum element bubbles up 
	the part of the array under consideration to reach its 
	exact location. The index 'i' keeps track of that location  
	where the current maximum would go. The index 'j' scans the 
	array upto that location for the maximum. */
	for (i=n-2; i>=0; i--) {    
		for (j=0; j<=i; j++) {
			compare_sort++;   
			if (array[j] > array[j+1]) { /* Checks if swap is needed */       
				/* The next 3 lines do the swap */
				t = array[j];          
				array[j] = array[j+1];     
				array[j+1] = t;        
			}
		}
	}

	printf("\n The sorted output is ::> "); 
	for(i=0;i<n;i++) {
		printf(" %d ",array[i]);
	} 
	printf ("\n The number of comparisons for sort is %d \n", compare_sort);

	/* Now, we do the binary search part */
	/* Take the element for binary search*/ 
	printf("\n What is the element you want to do binary search with::>");
	scanf("%d", &x);  

	/* The initialization part. low and high stores the two indices within 
	which we trap the search. */
	low = 0, high = n-1; j = -1; 
	while((low <= high) && (j==-1)) { /* The condition for the loop */
		mid = (low + high)/2; /* mid is the location where we test for equality */
		compare_binsearch++;
		if(x == array[mid]) { 
			j = mid; 
		}
		/* We decide which part of the array to focus on */
		else if( x < array[mid]) 
			high = mid - 1; 
		else 
			low = mid + 1; 
	}
	if(j==-1)
		printf("\n The number is not in the array; %d comparisons done.\n",compare_binsearch);
	else
		printf("\n The array index where %d occurs is %d. %d comparisons done. \n",x,j,compare_binsearch);

	/* Take the element for finding exact sum as in Q1(e)*/ 
	printf("\n What is the element to which two elements in the array sums to::>");
	scanf("%d", &z);  

	/* Initialization part */
	low = 0; high = n-1; 
	/* The logic is as follows. We operate on the sorted array.
	There are two indices -- low and high. low increases to the 
	right and high decreases to the left. If */
	while(low < high) { /* The condition check on the two indices */
		expect = array[low]+array[high];/* The sum of the two elements indexed by low & high */
		compare_sum++;
		if(expect == z) { /* Got a pair that sums to z */
			printf("\n array[%d]+array[%d]=%d \n",low,high,z);
			low++; high--; /* We keep looking for other pairs */
			flag=1;
		}
		else if(expect < z) 
			/* If the sum is less than z; then we look for greater sum by increasing low */
			low++; 
		else 
			/* If the sum is greater than z; then we look for lesser sum by decreasing high */
			high--;     
	} 
	if(flag==0)
		printf("\n No pair of elements in the array sum up to %d \n",z);

	printf("\n The total number of comparisons is %d \n",compare_sum);
	return 0;
}