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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 请问,一般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;
} |