Search an array of integers for a VAL value entered on the keyboard. Display the position of VAL if it is in the array, otherwise display a corresponding message. The INDEX value that is used to memorize the position of the value in the array, will have the value -1 as long as VAL was not found.

Condition: Table A must be sorted

Method:

• Compare the searched number to the value in the middle of the array,
• if there is a tie or if the array is exhausted, stop the treatment with a corresponding message.
• If the value sought precedes the current value of the array, continue the search in the half-array to the left of the current position.
• if the desired value follows the current value of the array, continue the search in the half-array to the right of the current position.

#include<stdio.h>
#include<conio.h>
#define SIZE 50
void main()
{
	int A[SIZE], N, val;
	int i;
	int index;
	int lower, middle, upper;

	do {
		printf("Enter the dimension: ");
		scanf("%d", &N);
	} while (N <= 0 || N > SIZE);


	// reading the array in ascending order
	printf("Enter A[0]: ");
	scanf("%d", &A[0]);
	for (i = 1; i < N; i++)
	{
		do{
			printf("Enter A[%d]: ", i);
			scanf("%d", &A[i]);
		}while(A[i]<A[i-1]);
	}

	printf("Enter the element to find: ");
	scanf("%d", &val);


 	/* Display the array */
 	printf("Given array : \n");
 	for (i=0; i<N; i++)
    		printf("A[%d]=%d\n",i, A[i]);
 	printf("\n");


 	/* Initializing the boundaries of the search domain */
 	lower=0;
 	upper=N-1; // at the first i consider searching the entire array
 	/* finding the index of the val */
 	index=-1;
 	while ((lower<=upper) && (index==-1))
        {
         	middle=(upper+lower)/2;
         	if (val < A[middle])
               		upper=middle-1; 	// consider the left sub-array
         	else 
			if (val > A[middle]) 
               			lower=middle+1; 	// consider the right sub-array
         		else
               			index=middle;
        }


 	if (index==-1)
     		printf("%d not found in the array.\n", val);
  	else
     		printf("%d is found at index %d.\n", val, index);

	getch();
}