upper_bound & lower_bound

[kizhvac kampazitr]

I need to write the function upper_bound & lower_bound manually ,not to use ready-made...

I did something like this ))
Where is the error ?

int upper_bound(const std::vector<int>& v, int b)
{
	int start = 0;
	int end = v.size();
	int count = end - start + 1;
	while(count > 0)
	{
		int step = count / 2;
		if (v[step] >= b)
		{
			start = ++b;
			count -= step + 1;
		}
		else
			count = step;
	}
	return start;
}


int lower_bound(const std::vector<int>& v, int a)
{
	int start = 0;
	int end = v.size();
	int count = end - start + 1;
	while(count > 0)
	{
		int step = count / 2;
		if (v[step] < a)
		{
			start = ++a;
			count -= step + 1;
		}
		else
			count = step;
	}
	return start;
}

[gunnerfunner]

Where is the error ?

if you wrote the program you should be telling us if there's an error, where it is and what sort of help you expect from here

[kizhvac kampazitr]

1D logistics
In a 1D world Axisland all the objects are on a single 1D axis and can be specified by a single coordinate x. Several objects can have the same coordinate. Your task, knowing the locations of objects, is to answer a big number of requests like “How many objects are in the interval [A,B]?”.
The first line of input consists of a number N - the number of objects in Axisland. The next line contains N integers - object coordinates. The third line has a number M - the number of requests, followed by M lines of requests. Each request is a pair of integers A and B (A <= B). For each request the program shall output a single integer - the the number of objects in Axisland from the given interval [A,B].
Requirement: Each request shall be processed in O(logN) time.

Input
10
1 1 7 1 2 1 7 6 -1 0
10
0 0
0 10
-10 10
1 2
1 3
10 20
-20 -10
8 8
7 8
-1 0

Output

1
9
10
5
5
0
0
0
2
2

my code

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

void SelectionSort(std::vector<int>& v)
{
	for(int i = 0; i < v.size() - 1; ++i)
	{
		int min_ind = i;
		for(int j = i + 1; j < v.size(); ++j)
		{
			if(v[j] < v[min_ind])
				min_ind = j;
		}
		std::swap(v[i], v[min_ind]);
	}
}

int upper_bound(const std::vector<int>& v, int start, int end, int b)
{
	int count = end - start;
	while(count > 0)
	{
		int step = count / 2;
		if(v[step] < b)
		{
			start = ++b;
			count -= step + 1;
		}
		else
			count = step;
	}
	return start;
}


int lower_bound(const std::vector<int>& v, int start, int end,  int a)
{
	int count = end - start;
	while(count > 0)
	{
		int step = count / 2;
		if(v[step] >= a)
		{
			start = ++a;
			count -= step + 1;
		}
		else
			count = step;
	}
	return start;
}

int main()
{
	int n;
	std::cin >> n;
	std::vector<int> v(n);
	for(int i = 0; i < n; ++i)
		std::cin >> v[i];
	SelectionSort(v);
	int m;
	std::cin >> m;
	int a, b;
	for(int i = 0; i < m; ++i)
	{
		std::cin >> a >> b;
		std::cout << upper_bound(v, 0, v.size(), b) - lower_bound(v, 0, v.size(), a) + 1 << "\n";
	}
}

my program's Output

0
12
21
4
5
24
18
12
12
1

[JLBorges]

std::size_t lower_bound( const std::vector<int>& seq, std::size_t start,
                         std::size_t end, int value )
{
    if( start == end ) return start ; // empty sequence
    else if( (end-start) == 1U ) return seq[start] < value ? end : start ;

    const auto mid = start + (end-start) / 2 ;
    if( seq[mid] < value ) return lower_bound( seq, mid+1, end, value ) ;
    else return lower_bound( seq, start, mid, value ) ;
}

std::size_t lower_bound( const std::vector<int>& seq, int value )
{ return lower_bound( seq, 0, seq.size(), value ) ; }

std::size_t upper_bound( const std::vector<int>& seq, int value )
{
    if( value == std::numeric_limits<int>::max() ) return seq.size() ;
    else return lower_bound( seq, 0, seq.size(), value+1 ) ;
}

http://coliru.stacked-crooked.com/a/bff0b576de91f352

[kizhvac kampazitr]

JLBorges thanks for the help