Windows 7 in USB Drive (USB HDD/Removabl
晒U盘，顺便对比USB2.0和USB3.0
Nov
15
非递归二分查找一个元素在有序数组中应处的位置 
@2019-03-19 STL里的lowerbound算法简单有效。
该元素在数组中不一定存在，只是要找一个i，使得 arr[i] <= t <= arr[i+1]。非递归的代码看起来真蛋疼。
转载请注明出自 ，如是转载文则注明原出处，谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
该元素在数组中不一定存在，只是要找一个i，使得 arr[i] <= t <= arr[i+1]。非递归的代码看起来真蛋疼。
//区间是 [s, e)，左闭右开，类似STL。
int binsearch(int arr[], int t, int s, int e)
{
int left = s, right = e, mid;
while (left < right)
{
mid = left + (right - left) / 2;
if (arr[mid] == t)
return mid;
else if (arr[mid] < t)
{
//right most OR ...right here
if (mid + 1 >= right || t < arr[mid + 1])
return mid;
else
left = mid + 1;
}
else /* arr[mid] > t */
{ //left most OR ...right here
if (mid - 1 < left || arr[mid - 1] <= t)
return mid - 1;
else
//11.18.DELETED: right = mid - 1;
right = mid; //[11.18.update]发现这里是个BUG……
}
}
return -2; //bad range
}
int binsearch(int arr[], int t, int s, int e)
{
int left = s, right = e, mid;
while (left < right)
{
mid = left + (right - left) / 2;
if (arr[mid] == t)
return mid;
else if (arr[mid] < t)
{
//right most OR ...right here
if (mid + 1 >= right || t < arr[mid + 1])
return mid;
else
left = mid + 1;
}
else /* arr[mid] > t */
{ //left most OR ...right here
if (mid - 1 < left || arr[mid - 1] <= t)
return mid - 1;
else
//11.18.DELETED: right = mid - 1;
right = mid; //[11.18.update]发现这里是个BUG……
}
}
return -2; //bad range
}
欢迎扫码关注：
转载请注明出自 ，如是转载文则注明原出处，谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
