Searching 44

QUESTION

Given an array arr[0 .. n-1] of distinct integers, the task is to find a local minima in it. We say that an element arr[x] is a local minimum if it is less than or equal to both its neighbors.\n\nFor corner elements, we need to consider only one neighbor for comparison.\nThere can be more than one local minima in an array, we need to find any one of them.

“TESTCASE_1”: “6\n4 3 1 14 16 40\n###—###SEPERATOR—###—\nIndex of a local minima is 2”, “TESTCASE_2”: “5\n23 8 15 2 3\n###—###SEPERATOR—###—\nIndex of a local minima is 0”, “TESTCASE_3”: “3\n1 2 3\n###—###SEPERATOR—###—\nIndex of a local minima is 1”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

import java.io.*;
import java.util.*;
 
class TestClass
{
     

    public static int localMinUtil(int[] arr, int low, int high, int n)
    {
         

        int mid = low + (high-low)/2;
         
     
        if(mid == 0 || arr[mid-1] > arr[mid] && mid == n-1 || arr[mid] < arr[mid+1])
                return mid;
         
       
        else if(mid > 0 && arr[mid-1] < arr[mid])
                return localMinUtil(arr, low, mid-1, n);
         
      
        return localMinUtil(arr, mid+1, high, n);
    }
     
 
    public static int localMin(int[] arr, int n)
    {
        return localMinUtil(arr, 0, n-1, n);
    }
     
     
    public static void main (String[] args) 
    {
         
      Scanner sc=new Scanner(System.in);  
     int n=sc.nextInt();
      int arr[]=new int[n];
      for(int i=0;i<n;i++)
        arr[i]=sc.nextInt();
        System.out.println("Index of a local minima is " + localMin(arr, n));
    
    }
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.