#include <stdio.h>

// binary_search - 2 way search (left,right)
// idx - 0 1 2 3 4 5 6 7 8 9
// arr - 1 2 3 4 5 6 7 8 9 10

// Sample 0
// key - 15
// n - 10

// l_idx = 0
// r_idx = 9
// m_dix = 5

// arr[5] = 6
// 15 - 6 -> 15 is greater than 6 search right side
// l_idx = m_idx = 5
// r_idx = 10

// m_idx = 7
// arr[7] = 8

// 15 - 8 -> 15 is greater than 8 , search on right side
// l_idx = 7
// r_idx = 10
// m_idx = 8

// arr[8] = 9
// 15 - 9 -> 15 is greater than 9, search on right side
// l_idx = 8
// r_idx = 10
// m_idx = 9

// arr[9] = 10
// 15 - 10 -> 15 is greater than 10, search on right side
// l_idx = 9
// r_idx = 10
// m_idx = 9

// arr[9] = 10
// 15 - 10 -> 15 is greater than 10, search on right side

// l_idx == r_idx - the element is not there so break the loop

// Sample 1
// key - 5
// n - 10

// l_idx = 0
// r_idx = 10
// m_idx = 5

// arr[5] = 6
// 5 - 6 -> 6 greater than 5 so search in the left side
// r_idx = m_idx = 5
// l_idx = 0

// m_idx = (0+5) / 2 = 2
// arr[2] = 3
// 5 - 3 -> 3 smaller than 5 so search in the right side
// l_idx = m_idx = 2
// r_idx = 5

// m_idx = (2+5) / 2 = 3
// arr[3] = 4
// 5 - 4 -> 4 smaller than 5 so search in the right side
// l_idx = 3
// r_idx = 5

// m_idx = (5+3) / 2 = 4
// arr[4] = 5

// 5 - 5 -> Element found

// Sample 2
// key - 8
// n - 10

// l_idx = 0
// r_idx = n = 10
// m_idx = (l_idx + r_idx) / 2 = 5

// 8 - 6  6 smaller so search on right side of the array

// l_idx = m_idx = 5
// r_idx = 10

// m_idx = (5+10) / 2 = 7
// arr[7] = 8  - 8 8 is equal found our element

// recursion - calling a function within itself (infinite loop)

//  write a c program using binary search if element is present return its index else return -1

int binarySearch(int arr[], int l, int r, int key)
{
    while (l < r)
    {
        int m = (l + (r-1)) / 2;
        // check if key is present at mid
        if (arr[m] == key)
        {
            return m;
        }

        //  if key is greater, ignore the left half
        if (arr[m] < key)
        {
            l = m + 1;
        }
        else
        // if key is smaller, ignore the right half
        {
            r = m - 1;
        }
    }
    return -1;
}

int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int key = 5;

    int result = binarySearch(arr, 0, 9, key);

    if (result != -1)
    {
        printf("Key is present in index :: %d", result);
    }
    else
    {
        printf("Key is not present");
    }

    return 0;
}