Search in rotational sorted array[ Microsoft – Amazon – FlipKart ]

Problem: Find a value from a rotational sorted array.

Solution Hint: binary search.

Link

#include <stdio.h>

int arr[100010];
int bin_search(int lw,int hi,int v)
{
    if(v<arr[lw] || v>arr[hi])
    return 0;
    int mid;
    while(lw<=hi)
    {
        mid=(lw+hi)/2;
        if(arr[mid]==v)
        {
            printf("%d\n",mid);
            return 1;
        }
        else if(arr[mid]<v)
        lw=mid+1;
        else if(arr[mid]>v)
        hi=mid;
    }
    return 0;
}

int main() {
	//code
	int t,i,j,n,val,a,idx;
	int f=0;
	int lw,mid,hi;
	scanf("%d",&t);
	while(t--)
	{
	    scanf("%d",&n);
	    val=100010;
	    f=0;
	    for( i=0;i<n;i++)
    	{
    	    scanf("%d",&arr[i]);
    	    if(arr[i]<val)
    	    {
    	        val=arr[i];
    	        idx=i;
    	    }
    	}
    	scanf("%d",&a);
     	lw=idx;hi=(idx+n-1)%n;
    	f=bin_search(0,hi,a);
    	if(f==0)
    	f=bin_search(lw,n-1,a);
    	if(f==0)
    	printf("-1\n");
	}
	
	return 0;
}