-3

I know it is not a good question to ask here. But I did my best in finding some good C code for lower and upper bound without using STL. But I wasn't able to find the right one. Please provide me proper code for both of these and apologise for asking such question.

hiag
  • 21
  • 1
  • 6
  • 2
    The upper bound of what? – Nick ODell Jan 17 '19 at 04:29
  • 2
    STL is the [Standard Template Library](https://en.wikipedia.org/wiki/Standard_Template_Library), a now mostly obsolete ***C++*** library. So no matter what you do, in C you will never directly use the STL. – Some programmer dude Jan 17 '19 at 04:30
  • 3
    And please take some time to read [the help pages](http://stackoverflow.com/help), especially the sections named ["What topics can I ask about here?"](http://stackoverflow.com/help/on-topic) and ["What types of questions should I avoid asking?"](http://stackoverflow.com/help/dont-ask). Also take [the SO tour](http://stackoverflow.com/tour), read about [how to ask good questions](http://stackoverflow.com/help/how-to-ask), as well as [this question checklist](https://codeblog.jonskeet.uk/2012/11/24/stack-overflow-question-checklist/). Lastly learn how to create a [mcve]. – Some programmer dude Jan 17 '19 at 04:32
  • Do you want an answer for C or for C++? – Eric Postpischil Jan 17 '19 at 04:35
  • Don't confuse C and C++; they are two very different languages. Se also [this answer](https://stackoverflow.com/a/54222375/841108) – Basile Starynkevitch Jan 17 '19 at 05:48

1 Answers1

1

Update for response

I hope this will work. Where A is sorted array and we are looking value K. 

int UpperBound(int A[],int N,int K){
    int low , high , mid ;
    low = 1 ;
    high = N ;
    while(low <= high){
        mid = ( low + high ) / 2 ; // finding middle element 
        if(A[mid] > K && ( mid == 1 || A[mid-1] <= K )) // checking conditions for upperbound
            return mid ;
        else if(A[mid] > K) // answer should be in left part 
            high = mid - 1 ;
        else                // answer should in right part if it exists
            low = mid + 1 ;
    }
    return mid ; // this will execute when there is no element in the given array which > K
}


int LowerBound(int A[],int N,int K){
    int low , high , mid ;
    low = 1 ;
    high = N ;
    while(low <= high){
        mid = ( low + high ) / 2 ; // finding middle element 
        if(A[mid] >= K && ( mid == 1 || A[mid-1] < K )) // checking conditions for lowerbound
            return mid ;
        else if(A[mid] >= K) // answer should be in left part 
            high = mid - 1 ;
        else                // answer should in right part if it exists
            low = mid + 1 ;
    }
    return mid ; // this will execute when there is no element in the given array which >= K
}
Shakil
  • 4,520
  • 3
  • 26
  • 36
  • for searchValue=1, it is giving: upperbound Index=2 and lowerbound index= 0. This is creating confusion because for 1, upper and lower bound should be index=1. Where to do changes in code? – hiag Jan 17 '19 at 05:00
  • Very good catch, i have edited my code. Please check this. – Shakil Jan 17 '19 at 05:07
  • the variable `upperbound` is declared, but never initialized to a known value, So accessing the contents is undefined behavior – user3629249 Jan 17 '19 at 05:29
  • I think upperBound should also initialize to -1 because of the case where arr[] = {0, 2, 3 , 4, 5} and searchValue = 6. In this case, there is no upper bound of 6 but code returns index 0 for lower bound and upper bound which is wrong. But here for 6 no upper bound and lower bound. – hiag Jan 17 '19 at 16:20
  • yes, good point. – Shakil Jan 17 '19 at 17:13
  • Actually, it is giving more wrong output for other cases. I found it when I am using this code for upper bound during the submission to an online judge platform. So, I don't think that this code will work. – hiag Jan 17 '19 at 17:56
  • @hiag i have updated my code. I hope this will work. – Shakil Jan 17 '19 at 18:06
  • for int ar[]={1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 7, 7, 8, 8, 8, 8, 9, 9, 10, 10, 10}; for searchValue=1 LowerBound=1, UpperBound=2. Please check this too. – hiag Jan 18 '19 at 06:04
  • this is suppose to start from 1 index. so lowerBound 1 and UpperBound 2 should be perfectly alright. just need to initial low as 0 and high = N - 1 for that. If you want that. – Shakil Jan 18 '19 at 06:07