a*******y
发帖数: 1040 | 1 sorted array with repeated elements
for given element, find out its range.
e.g. A A B B B B B C C D D E F G, given B, the output should be [2, 6]
binary search的变种
我感觉这个不是O（logn）啊
code是发现repeat次数的
int binarySearch(char* charset, int start, int end, char target)
{
if (charset == NULL) return 0;
if (start == end)
{
if (charset[start] == target) return 1;
else return 0;
}
int mid = start + (end-start)/2;
int left = 0, right = 0;
left = binarySearch(charset,start,mid-1,target);
right = binarySearch(charset, mid+1, end, target);
return (charset[mid] == target ? left+right+1 : left + right);
} | d****n
发帖数: 1637 | 2 size_t left, right, found;
size_t found=bsearch(array, start, end, target );
left=right=found;
while (array[left--]==target) left=found;
while (array[right++]==target) right=found;
return left, right | S**I
发帖数: 15689 | 3 http://www.cplusplus.com/reference/algorithm/equal_range/
【在 a*******y 的大作中提到】
: sorted array with repeated elements
: for given element, find out its range.
: e.g. A A B B B B B C C D D E F G, given B, the output should be [2, 6]
: binary search的变种
: 我感觉这个不是O（logn）啊
: code是发现repeat次数的
: int binarySearch(char* charset, int start, int end, char target)
: {
: if (charset == NULL) return 0;
: if (start == end)
| a*******y
发帖数: 1040 | 4 No , worst case is O(n) for this
【在 d****n 的大作中提到】
: size_t left, right, found;
: size_t found=bsearch(array, start, end, target );
: left=right=found;
: while (array[left--]==target) left=found;
: while (array[right++]==target) right=found;
: return left, right
| d****n
发帖数: 1637 | 5 你也没说要求啊
【在 a*******y 的大作中提到】
: No , worst case is O(n) for this
| a*******y
发帖数: 1040 | | f*******n
发帖数: 12623 | 7 Functions to find the left and right bounds, both log(n):
// left bound, inclusive
int binarySearch_left(char* arr, int len, char value) {
int low = 0, high = len-1, mid;
while (low < high) {
mid = (low + high) / 2;
if (arr[mid] >= value)
high = mid - 1;
else
low = mid + 1;
}
return low;
}
// right bound, inclusive
int binarySearch_right(char* arr, int len, char value) {
int low = 0, high = len-1, mid;
while (low <= high) {
mid = (low + high) / 2;
if (arr[mid] > value)
high = mid - 1;
else
low = mid + 1;
}
return low - 1;
} | f*******n
发帖数: 12623 | 8 那个code是O(n)
【在 a*******y 的大作中提到】
: sorted array with repeated elements
: for given element, find out its range.
: e.g. A A B B B B B C C D D E F G, given B, the output should be [2, 6]
: binary search的变种
: 我感觉这个不是O（logn）啊
: code是发现repeat次数的
: int binarySearch(char* charset, int start, int end, char target)
: {
: if (charset == NULL) return 0;
: if (start == end)
| S**I
发帖数: 15689 | 9 Read the source code of equal_range in a C++ implementation. In both VC and
GCC, implementation of equal_range is based on lower_bound and upper_bound,
both of which have log(n) complexity if the range to be searched is a sorted
array. So equal_range has complexity 2log(n).
【在 a*******y 的大作中提到】
: 要log（n)的
| l****c
发帖数: 782 | 10
you lost one more step in each function. Think about "ABBC". Your approach
will find 0 as the left edge.
Try to add this before return in:
if (array[low]
else return low;
【在 f*******n 的大作中提到】
: Functions to find the left and right bounds, both log(n):
: // left bound, inclusive
: int binarySearch_left(char* arr, int len, char value) {
: int low = 0, high = len-1, mid;
: while (low < high) {
: mid = (low + high) / 2;
: if (arr[mid] >= value)
: high = mid - 1;
: else
: low = mid + 1;
| a*******y
发帖数: 1040 | 11 我觉得他应该把第一个那个“<=”改成< 就行了
【在 l****c 的大作中提到】
:
: you lost one more step in each function. Think about "ABBC". Your approach
: will find 0 as the left edge.
: Try to add this before return in:
: if (array[low]: else return low;
| a*******y
发帖数: 1040 | 12 吧这个 if (arr[mid] >= value) 中的大于等于改成《
第二个function return hi
我来贴两个吧，test过了
int binarySearchLower(int A[], int l, int h, int k) {
int lo = l;
int hi = h;
while (lo <= hi) {
int mid = lo + (hi-lo)/2;
if (A[mid] < k)
lo = mid+1;
else
hi = mid-1;
}
return lo;
}
int binarySearchUpper(int A[], int low, int high, int k)
{
int lo = low;
int hi = high;
while (lo <=hi)
{
int mid = lo + (hi-lo)/2;
if (A[mid] > k)
hi = mid - 1;
else
lo = mid + 1;
}
return hi;
}
【在 f*******n 的大作中提到】
: Functions to find the left and right bounds, both log(n):
: // left bound, inclusive
: int binarySearch_left(char* arr, int len, char value) {
: int low = 0, high = len-1, mid;
: while (low < high) {
: mid = (low + high) / 2;
: if (arr[mid] >= value)
: high = mid - 1;
: else
: low = mid + 1;
| f*******n
发帖数: 12623 | 13 Copying mistake
// left bound, inclusive
int binarySearch_left(char* arr, int len, char value) {
int low = 0, high = len-1, mid;
while (low <= high) {
mid = (low + high) / 2;
if (arr[mid] >= value)
high = mid - 1;
else
low = mid + 1;
}
return low;
}
// right bound, inclusive
int binarySearch_right(char* arr, int len, char value) {
int low = 0, high = len-1, mid;
while (low < high) {
mid = (low + high) / 2;
if (arr[mid] > value)
high = mid - 1;
else
low = mid + 1;
}
return low - 1;
} |
|
