Binary Search using recursion

Given an sorted array: {1,5,6,10,19,31,72}

Solution:
Binary search only works on sorted array.
Calculate middle location of array and check the element which element to be searched.
Since array is sorted, if mid element is less then search item, then element is bound to be in the second half of list. In next steps, search within the respective part of the list
Start marker of array become middle +1 location, end remains same.
start= mid+1

Otherwise if the mid element is greater than search item, then element will be in the first half of list.
End marker of array become middle -1 location, start remains same.

Complexity: O(N/2)

#include <stdio.h>

int binarySearch(int array[],int start,int end,int search) {
if( start > end) {
                // A base condition
                // Happens when list does not contain value
return -1;
}

int mid = (int) ((start + end)/2);

if(  array[mid] > search) {
binarySearch(array, start, mid-1, search);
}
else if ( array[mid] < search) {
binarySearch(array, mid+1, end, search);
}

else {
               // A Base condition
              // Element found, return its position
return mid+1;
}
}

int main() {
    int arr[] = {1,5,6,10,19,31,72};
    int size = sizeof(arr)/sizeof(arr[0]);

    int pos = -1;
    int searchItem = 1;
 
    pos = binarySearch(arr, 0, 5,searchItem);
    if(pos == -1) {
        printf("%d not found in list",searchItem);
    }
    else {
        printf("%d found at location %d",searchItem,pos);
    }
    return 0;
}

Output:
1 found at location 1

Factorial Using recursion

Factorial of number n (n!) is 1* 2 * ... (n-1) *  n
5! = 5*4*3*2*1 = 120

Checkout: Factorial without recursion

Solution: 
Recursion is the process in which functions calls itself until some base condition is met. Recursion helps in writing shorter functions by dividing a problem into small parts and then solving that problem using a same function again.

We know that n! = 1 for n = 0, n! = n * (n-1)!  for n > 0
For writing a recursive method we can use base condition when n become 1 and call the recursive method with (n-1) at each call.

#include<stdio.h>

int factorial(int n) {
     if(n>0) {
           return n * factorial(n-1);
     }
     else {
           return 1;
     }
}

int main()
{
    int num =5;
    printf("Factorial of %d : %d", num, factorial(num));
}

Output:

Factorial of 5 : 120                                                                                                          

                    

Finding whether a number exists as sum of two array elements in a sorted array

Given the array{-5,-2,7,8,9,10,12}

Find whether sum 8 is possible

As element no.2 (-2) and element no.7(10) are present the sum of the two is 8

Solution:  As the array is sorted, we can leverage this property and come up with an approach which is similar to binary searching

Start with two markers at start and end of the array

Sum the two numbers at start and end marker

if sum is greater than given number, decrease the end marker 

if sum is less than given number, advance the start marker

Break if desired sum is found or start becomes greater than or equal to end

Complexity: O(n)

#include <stdio.h>
int main()
{
    int a[] = {-5,-2,7,8,9,10,12};
    
    int sum =8;
    
    int found_flag = 0;
    int size = sizeof a / sizeof a[0];
    printf("\nSize of array %d", size);
    int start = 0;
    int end = size-1;
    
    while(start<=end) {
        if((a[start]+a[end])<sum) {
            start++;
        }
        else if ((a[start]+a[end]>sum)) {
            end--;
        }
        else {
            found_flag++;
            break;
        }
    }
    
    if(found_flag) {
     printf("\nElement at location(%d):%d and location(%d):%d has sum:%d", start+1,a[start],end+1,a[end],sum);
    }
    else {
        printf("\nNot found !!");
    }
    return 0;
}

Output:

Size of array 7                                                                                                               

Element at location(2):-2 and location(6):10 has sum:8 

Finding whether a number exists as sum of two array elements in an unsorted array

Given the array{2, 10,9,7,8 ,-2}

Find whether sum 8 is possible

As element no.2 (10) and element no.6(-2) are present the sum of the two is 8

Solution: Taking an Sum minus the fixed element, we scan through rest of the array to find another element matching

Complexity: O(n^2)

#include <stdio.h>

int main()

{

    int a[6] = {2, 10,9,7,8 ,-2};

    

    int sum = 8;

    

    int flag = 0;

    int size = sizeof a / sizeof a[0];

    printf("\nSize of array %d", size);

    int i=0;

    int j =0;

    for (i= 0; i<size-1; i++) {

        for(j=i+1; j <size;j++) {

            if(sum-a[i] == a[j]) {

                flag++;

                break;

            }

        }

        if(flag==1) {

            break;

        }

    }

    

    if(flag) {

     printf("\n Element at location(%d):%d and location(%d):%d has sum:%d", i+1,a[i],j+1,a[j],sum);

    }

    else {

        printf("Not found !!");

    }

    return 0;

}

Output:

Size of array 6                                                                                                               

 Element at location(2):10 and location(6):-2 has sum:8