c***g
发帖数: 472 | 1 请问，一般binary search都是要么返回index，要么返回不存在吧？
如果，需要在不存在的情况下，返回小于那个元素的最小值的index，怎么做？
比如
1 3 5 7 9 11
输入 6
返回2， 对应的是5
输入 12，
返回6，对应的是11
输入-1
返回-1， 表示最小的 |
l*****a
发帖数: 14598 | 2 int lo=0;
int hi=size-1;
while(lo
{
int mid=lo+(hi-lo)/2;
if(a[mid]==target) return mid;
else if(a[mid]>target) hi=mid;
else lo=mid;
}
if(a[hi]<=target) return hi;
else if(a[lo]<=target) return lo;
else return -1;
【在 c***g 的大作中提到】
: 请问，一般binary search都是要么返回index，要么返回不存在吧？
: 如果，需要在不存在的情况下，返回小于那个元素的最小值的index，怎么做？
: 比如
: 1 3 5 7 9 11
: 输入 6
: 返回2， 对应的是5
: 输入 12，
: 返回6，对应的是11
: 输入-1
: 返回-1， 表示最小的
|
a********d
发帖数: 195 | 3 是不是加个条件就行了？
public static int bsII(int[] arr, int target)
{
int leftIdx = 0;
int rightIdx = arr.Length - 1;
int mid = 0;
if (target < arr[0]) return -1;
if (target > arr[rightIdx]) return rightIdx;
while (leftIdx < rightIdx)
{
mid = (leftIdx + rightIdx) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target)
{
if (leftIdx == mid) return mid;
leftIdx = mid;
}
else
{
rightIdx = mid;
}
}
return mid;
} |
