Reputation: 53

How to find the index of the max value from the array ,smaller or equal to the input

The problem is somewhat like,to find the maximum reachable point in the path.Lets say we have an array of 6 elements. Assuming the array is sorted. Value of first element of the array is zero. Considering the elements of the array are {'0','200',' 375', '550', '750','950'}.
Let say we have to input a value between 0 and 950. We have to return the index of the max value from the array smaller or equal to the input value.
I am trying to get this done using while loop but i am stuck!!! Here is my code

  void  compute_min_refills(int value, int n, vector<int>  stops) {
     int currentrefill=0,num=0,lastrefill=0;
 lastrefill = currentrefill;
    while(currentposition <= n && stops[currentposition + 1] - stops[lastposition] < Value){ 
        currentposition = currentposition + 1;
    }
    cout<<currentposition<<' ';

}

Please help to resolve this.

Upvotes: 0

Answers (8)

A M

Reputation: 15277

Up to now 7 answers. But I am really surprised that nobody provided the standard function for that. For such kind of searches, there is a dedicated function, specifically designed for that purpose: std::upper_bound.

Please read about it here

This function will return an iterator. If you want to know the index, then simple use std::distance. And since we want to have not the greater, but smaller or equal value, we will additionally use std::prev

Then, all boils down to a very simple one-liner.

Please see the below example code with some test vector:

#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>

int main() {
    
    std::vector testValues{0,100,199,200,201,400,949,950,10000};
    
    std::vector data{0, 200, 375, 550, 750, 950};
    
    for (const int t : testValues) {
        
        std::cout << t << '\t' << std::distance(data.begin(),std::prev(std::upper_bound(data.begin(), data.end(), t)))<< "\n";
    }
    return 0;
}

The result will be:

Upvotes: 0

Amir Kadyrov

Reputation: 1288

Use std::find_if algorithm with reverse iterators

int input = 400;
int arr[] = { 0, 200, 375, 550, 750, 950 };
auto it = std::find_if(std::rbegin(arr), std::rend(arr), [&input](const int Value) { return Value <= input; });
if (it != std::rend(arr)) {
    std::cout << "Value=" << *it << " with index=" << std::distance(it, std::rend(arr)) - 1 << std::endl;
}
else {
    std::cout << "Value not found" << std::endl;
}

Output:        
Value=375 with index=2

or reverse loop

int input = 400;
int arr[] = { 0, 200, 375, 550, 750, 950 };
for (auto beg = std::rbegin(arr); beg != std::rend(arr); ++beg)
    if (*beg <= input) {
        std::cout << "Value=" << *beg << " with index=" << (std::rend(arr) - beg - 1) << std::endl;
        break;
    }
    
Output:        
Value=375 with index=2

or binary search may be faster on big data

int input = 400;
int arr[] = { 0, 200, 375, 550, 750, 950 };
auto beg = std::begin(arr);
auto end = std::end(arr);
auto mid = std::begin(arr) + (end - beg) / 2;
while (mid != end && *mid != input) {
    if (input < *mid) {
        end = mid;
    }
    else {
        if (mid + 1 == end || *(mid + 1) > input) {
            break;
        }
        beg = mid + 1;
    }
    mid = beg + (end - beg) / 2;
}
if (mid != end) {
    std::cout << "Value=" << *mid << " with index=" << std::distance(std::begin(arr), mid) << std::endl;
}
else {
    std::cout << "Value not found" << std::endl;
}

Output:        
Value=375 with index=2

Upvotes: 2

Deepak Patankar

Reputation: 3282

This is my understanding of the approach you were trying, you want to reach till the point you can, and once your value gets over, you want to print the index till where you have reached.

All the solutions given here works correct, are easy to read and are more efficient. Here I would like to suggest a few things that you can fix in your code and algorithm:

You should not loop till <=n but till n-2 as you are checking for next position at line stops[currentposition + 1]. The last index of the array is n-1 and you should not access the element at an index greater than that.
You have created a variable lastposition, but you aren't updating it in the loop. Also, we don't need a lastposition variable, as it will be currentPosition-1.
I am not sure, but you wanted to check whether you will be able to go to the next position. For the same, you are comparing stops[currentposition + 1] - stops[lastposition] < Value. Here what you are trying to do is that with the given amount of fuel left will I be able to go further. But You didn't update the value in the loop.

I am attaching the code snippet after fixing few things in your code:

#include <iostream>
#include <vector>

using namespace std;

int compute_min_refills(int value, int n, vector<int>  stops){
    int currentposition = 0;
    while(currentposition < (n-1) && stops[currentposition + 1] - stops[currentposition] <= value){ 
        int fuelSpent = stops[currentposition + 1] - stops[currentposition];
        value = value - fuelSpent;
        currentposition = currentposition + 1;
    }
    return currentposition;
}

int main() {
    int  i = 0, val = 1000, n = 6;
    vector<int> vect{0, 200, 375, 550, 750, 950}; 
    cout<<compute_min_refills(val,6,vect);
}

Upvotes: 1

reyad

Reputation: 1432

What you need to do is a binary search. Its the most optimized solution as the array is sorted. You can read about it here.

I am providing the solution(code) below:

void compute_min_refills(int value, vector<int> stops) {
  // here, s denotes the start of stops
  // and, e denotes the end index of stops
  int s = 0, e = stops.size() - 1;
  // x would contain the index we're searching for
  // by default it is -1
  // if it does not change, it means
  // no such number exists which is less than or equal to value
  int x = -1;
  
  // as long as start is less than or equal end
  while(s <= e) {
    // finding middle index
    int m = (s+e) / 2;
    // check if m index satisfies the condition
    if(stops[m] <= value) {
      x = m;
      // if satisfies, then go forward
      // to check if another greater number
      // is there that satisfies the condition
      s = m + 1;
    } else {
      // if not satisfies, then go backwards
      e = m - 1;
    }
  }
  return x;
}

// now, you can just call compute_min_refills as follows
int x = compute_min_refills(value, stops);
// check if no such number exists
if(x == -1) {
  printf("no such number exists\n");
} else {
  // and print to see the result
  printf("%d\n", stops[x]);
}

Upvotes: 2

Sai

Reputation: 1700

You just need to traverse the array until you encounter a greater value. So whenever you encounter a greater element than the input value it means the previous element (in the array) was the largest smaller or equal element to the input value.

#include <iostream>

int main() {

    int arr[] = {0, 200, 375, 550, 750, 950}, i = 0, val = 400, n = 6;

    while (i < n and arr[i] <= val) {
        i += 1;
    }

    (i >= 1) ? (std::cout << i - 1) : (std::cout << "No element");

}

Upvotes: 2

Paul Baxter

Reputation: 1175

You only need to compare the current array value to the value that you are looking for.

currentposition = 0;
while (currentposition <= n && stops[currentposition] < value)
{
    ++currentposition;
}
cout << currentposition << ' ';

Upvotes: 2

Artavazd

Reputation: 175

try this:

int index = 0;
int newElement = 400
while (index < n && newElement >= stops[index])
{
    index++;
}
cout<<index-1;

Upvotes: 2

v37

Reputation: 57

Assuming n in your code is the size of the array called stops, then you can try to change the condition in the while loop to (currentposition < n && stops[currentposition] <= Value)

Upvotes: 2

How to find the index of the max value from the array ,smaller or equal to the input

Answers (8)

Related Questions