/*
 * Program to learn Binary Search
 *
 * https://www.programiz.com/dsa/binary-search
 */

#include <stdio.h>


/* Sorted array */
int array[] = { 3, 4, 5, 6, 7, 8, 9 };

/* Iterative Method */
int binarySearchI(int array[], int x, int low, int high) 
{
	/* Repeat until the pointers low and high meet each other */
	while (low <= high) 
	{
		int mid = low + (high - low) / 2;

		if (array[mid] == x)
			return mid;

		if (array[mid] < x)
			low = mid + 1;
		else
		high = mid - 1;
	}

	return -1;
}

/* Recursive Method */
int binarySearchR(int array[], int x, int low, int high) 
{
	if (high >= low) 
	{
		int mid = low + (high - low) / 2;

		/* If found at mid, then return it */
		if (array[mid] == x)
			return mid;

		/* Search the left half */
		if (array[mid] > x)
			return binarySearchR(array, x, low, mid - 1);

		/* Search the right half */
		return binarySearchR(array, x, mid + 1, high);
	}

	return -1;
}

/* Entry point to program */
int main() 
{
	int n;
	int x;
	int result;
	
	n = sizeof(array) / sizeof(array[0]);
	printf("Enter integer:\n");
	scanf("%d", &x);
	
	result = binarySearchI(array, x, 0, n - 1);
  
	if (result == -1)
		printf("Not found");
	else
		printf("Element %d is found by Iterative Method at index %d\n", x, result);
	
	result = binarySearchR(array, x, 0, n - 1);
  
	if (result == -1)
		printf("Not found");
	else
		printf("Element %d is found by Recursive Method at index %d\n", x, result);
  
	return 0;
}