/*****************************************************
 Program to search for an item using binary search
 *****************************************************/

#include <stdio.h>
#define SIZE 10

int binary_search(int arr[], int target); // function declaration

int main() 
{

    int arr[SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // sorted array
    int target; // number to be searched
    int index;  // index position of the target

    printf("Enter number to search: \n");
    scanf("%d", &target);

    index = binary_search(arr, target);  

    if(index !=  -1)
    {
        printf("Item %d found at index %d.", target, index);
    }
    else
    {
        printf("Item %d not found.", target);    
    }   

    return 0;
}

/*
 * binary_search() returns index position of the 
 * target item. Returns -1, if the target item is not found.
 */

int binary_search(int arr[], int target)
{
    /* 
       variables to keep track of the index positions
       where we will search in the array
    */
    int low = 0, up = SIZE - 1, midpoint;    

    while(low <= up)
    {
        midpoint = (low + up) / 2;  // calculate midpoint

        if(target > arr[midpoint])
        {
            // proceed search to the right portion
            low = midpoint + 1;
        }

        else if(target < arr[midpoint])
        {
            // proceed search to the left portion
            up = midpoint - 1;
        }

        else if(target == arr[midpoint])
        {
            // target value found. Return the index and exit the function
            return midpoint;
        }        
    }

    // target value not found, return -1 and exit the function
    return -1;
}