World Cup

Question:

Some teams qualified for the 2014 World Cup. The score of the teams were stored in an array in sorted order and array index is the represents the team. Index 0 represents the Team 1; index 1 represents the Team 2 and so on. If a score is given, then should find out which team got that score with a O(log(n)) time.  

 Since Ram wanted to solve this puzzle with binary search and he decided to write binary search himself.  But he cannot remember the logic of binary search .  Help Ram to write the program.

 Note:

Create the main() inside the class ‘BinarySearch

Function signature : public static int binarySearch(int[] ar,int size,int key)

Input and Output Format:

Refer sample input and output for formatting specifications.

Sample Input and Output 1:

Enter the number of Teams:

5

Enter the score:

12

16

23

45

67

Enter the score to be searched:

23

23 is the score of Team 3

Sample Input and Output 2:

Enter the number of Teams:

4

Enter the score:

12

34

45

77

Enter the score to be searched:

59

Score Not Found

Code:

BinarySearch.java

import java.util.Scanner;
class BinarySearch
{ public static int binarySearch(int arr[],int l,int r ,int x)
    { if(r>=l)
        { int mid=l+(r-1)/2;
          if(arr[mid]==x)
            return mid;
          if(arr[mid]>x)
            return binarySearch(arr,l,mid-1,x);
          return binarySearch(arr,mid+1,r,x);
        }
        return -1;
    }
    public static void main(String args[])
    { BinarySearch ob=new BinarySearch();
      Scanner b =new Scanner(System.in);
      
      System.out.println("Enter the number of Teams:");
      int n =b.nextInt();
      if(n==0||n<0)
        { System.out.println("Invalid Input");}
      else
          {int a[]=new int[100];
          System.out.println("Enter the score:");
          for(int i=0;i<n;i++)
          { a[i]=b.nextInt();}
          System.out.println("Enter the score to be searched:");
          int x=b.nextInt();
          if(x==0||x<0)
          { System.out.println("Invalid Input");}
          else
              {int result=ob.binarySearch(a,0,n-1,x);
              int r= result+1;
              if(result==-1)
                System.out.println("Score Not Found");
              else
                System.out.println(x+" is the score of Team "+r);}}
        }
}

Recommended:

Leave a Comment

Your email address will not be published. Required fields are marked *

x