Hello, I\'ve been stuck on this problem for a while and would like help. Write,

Question

Hello, I've been stuck on this problem for a while and would like help.

Write, in Java, a program with an efficient t algorithm that has time complexity O(logn) for solving the following problem:
• Given an array A holding N elements, such that A[0] < A[1] < A[2] < . . . < A[N-1].
• Determine whether there is an index k such that 0 <= k <= N-1 and A[k] = k.

*Please also submit a corresponding tester class to test the correctness of your code.
*Please analyze the time complexity of your algorithm and put your analysis in the comments of your codes

Example input/outputs:
1 1 2 3 4 5
>>True

1 0 1 2 3 4
>>False


Thanks in advance

Explanation / Answer

This logic runs with a complexity of 2logn, which means it belongs to O(log n). The program and the search case is offered here with. If you have any further queries, just get back to me.

import java.util.Scanner;
class BinarySearch
{
public static boolean BinSearch(int[] Array, int low, int high)
{
int mid;
if(low <= high)   //If you have elements in the array.
{
mid = (low + high) / 2; //Calculate the mid value.
if(mid == Array[mid]) //If mid value equals the Array element at that position.
return true;           //Your search succeeded. You can stop there.
else                   //If not proceed further with the 2 parts of the array.
{
BinSearch(Array, low, mid-1); //Run the same logic with the left part of the array.
BinSearch(Array, mid+1, high);//Run the same logic with the right part of the array.
}
}
return false;                //If Array exhausted, and your requirement has never been satisfied, return false.
}
public static void main(String[] args)
{
int[] Array = new int[10];
Scanner in = new Scanner(System.in);
System.out.print("Enter the number of elements: "); //Reads number of elements.
int n = in.nextInt();  
System.out.print("Enter "+n+" elements: "); //Reads n elements into the array.
for(int i = 0; i < n; i++)
Array[i] = in.nextInt();
System.out.println(BinSearch(Array, 0, n-1)); //Calls the function, with array boundary values.
}
}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.