Let's start with one of the important and common basic question in Searching - Binary Search!
This question is on DHONI and BINARY SEARCH technique!
Dhoni is famous for his strategic thinking and cool-headed decision making in cricket. He is now facing a crucial situation in a cricket match and needs your help to devise a strategy.
Given an array of integers representing the runs scored by the opposing team in each over of the match, Dhoni wants to determine the over where the opposing team's score reaches a certain milestone. He wants to employ a binary search algorithm to efficiently find this over.
Write a function findOverMilestone(int[] overs, int milestone) that takes in two parameters:
- overs: a sorted array of integers representing the runs scored by the opposing team in each over of the match. The array is sorted in ascending order.
- milestone: an integer representing the milestone score that the opposing team wants to achieve.
The function should return the over number (1-indexed) when the opposing team's total score equals or exceeds the milestone. If the milestone is not reached, return -1.
Dhoni wants you to ensure that your solution is optimized and employs binary search to find the over efficiently.
Test Cases:
- Input: overs = {1, 2, 3, 4, 5}, milestone = 3; Expected Output: 3
- Input: overs = {10, 20, 30, 40, 50}, milestone = 35; Expected Output: 4
- Input: overs = {5, 10, 15, 20, 25}, milestone = 30; Expected Output: -1
- Input: overs = {2, 4, 6, 8, 10}, milestone = 1; Expected Output: 1
- Input: overs = {3, 6, 9, 12, 15}, milestone = 14; Expected Output: 4
Ensure that your function passes these test cases to ensure its correctness.
SOLUTION
import java.util.*;
public class Program {
public static int findOverMilestone(int[] overs, int milestone)
{
int l = 0;
int r = overs.length - 1;
int res = -1;
while (l <= r)
{
int m = l + (r - l) / 2;
if (overs[m] >= milestone)
{
res = m;
r = m - 1;
}
else
{
l = m + 1;
}
}
return res == -1 ? -1 : res + 1;
}
public static void main(String[] args)
{
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] overs = new int[n];
for (int i = 0; i < n; i++) {
overs[i] = scanner.nextInt();
}
int milestone = scanner.nextInt();
int over = findOverMilestone(overs, milestone);
System.out.println(over);
}
}
Insights:
- 1. This program is solved using the traditional way of Binary Search. Explore the binary search's maximum number of iterations.
- Revise the basics of Arrays in Java and the indexing, why res+1 is applied in return statement instead of return!
- Be clear with the Scanner class and the uer input methods. Try solving problems without prompts in System.out.println.
- Try incorporating ternary operator instead of simple if else.
- Explore the built in binarySearch function with the help of the below coding snippet
Superrrbbbbb 👌
ReplyDeleteThanks! :)
Delete