Binary Search on array of numbers: C Code, O(logn)

Interview Question: Find Element

Problem Statement

There is an array of numbers where the number are continuously increasing until any position. After which they are continuously decreasing. Find the element where this has changed.

Solution

#include<stdio.h>

int find(int a[], int l, int r) ;
int main()
{

int a[20] = {2,4,7,3,2,1};
int l = 0;
int r = 5;

printf("%d ok", find(a, l, r));

}

// recursive code prefered
int find(int a[], int l, int r) {

while(l <= r) {
   
    int m = (l +r)/2;
       
    if(a[m] > a[m-1] && a[m] > a[m+1])
        return a[m+1];
   
    else if(a[m] < a[m-1] && a[m] > a[m+1])
        return a[m];
   
    else if(a[m-1] < a[m] && a[m] < a[m+1])
        return find(a, m+1, r);
   
    else if(a[m-1] > a[m] && a[m] > a[m+1])
        return find(a, l, m-1);
}

return -1;
}
       

Time Complexity: O(logn), binary search


If you find this blog somewhat helpful, please share it and Keep Visting....:)