Upper_bound

help
,
1

Here is my code to find the number of values less than or equal to the ‘value’ passed to the function. Please tell me the reason why this code should fail. Any test case would be helpful.
Thanks a lot.

 public static int search( int a[], int value){
   int low=0;
   int high=a.length-1;
   int ans=0;
   while(low<=high)
   {
     int mid=low+(high-low)/2;
     if(a[mid]<=value)
     {
       ans=mid+1;
       low=mid+1;
     }

     else
     {
       high=mid-1;
     }
   }
   return ans;
 }
2

Did you sort the array before checking ?

3

a.length returns the total size allocated to the array and not the number of elements present in it
so better pass the n value (i.e. the number of elements of the array) to the search function and assign high=n-1

4

@silvester14 can you send the full code

5

some small changes to your code …

  1. high = a.size() (for corner cases)
  2. high = mid in else part (as this can be a possoble ans)
  3. while(low < high) (to avoid infinite loop)
1 Like
6

Yes

7

import java.util.;
import java.io.;

public class Solution {

 public static void main(String[] args) {
   Scanner sc = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
   StringBuilder sb=new StringBuilder();
   int n=sc.nextInt();
   int m=sc.nextInt();
   int a[]=new int[n];
   int b[]=new int[m];
   for( int i=0;i<n;i++){
     a[i]=sc.nextInt();
   }
    Arrays.sort(a);
   for(int i=0;i<m;i++){
     b[i]=sc.nextInt();
     int num=search(a, b[i]);
     sb.append(num);
     sb.append(" ");
   }
   System.out.println(sb.toString());
 }
 public static int search( int a[], int value){
   int low=0;
   int high=a.length-1;
   int ans=0;
   while(low<=high)
   {
     int mid=low+(high-low)/2;
     if(a[mid]<=value)
     {
       ans=mid+1;
       if(mid+1<a.length&&a[mid+1]<=value)
       low=mid+1;
       else
       break;
     }

     else
     {
       high=mid-1;
     }
   }
   return ans;
 }

}

8

Can you explain why this should be like this?