求大神帮我写个二分查找的代码，今天想这个头都懵了。

只看该作者 · 2018-10-23 21:11

数组中最少会有1个字节为0xff，假如有多个0xff的话，它们在的地址一定是连续的。
查找第一个为0xff的元素下标。
查找最后一个为0xff的元素下标。
假定数组为char a[1024];

只看该作者 · 2018-10-23 21:19

可能描述不够准确，数组中所有的0xff所在地址都是连续的。
假如a[0]到a[10]区间都是0xff，那么其它位置一定没有0xff。

这应该符合二分查找的数据有序的要求。

只看该作者 · 2018-10-24 07:46

可以写，具体沟通q793281484

只看该作者 · 2018-10-24 08:18

这样的算法我一般到网上找找源代码再看看

3万 · 2018-10-24 08:40

//这种没有排序的数据结构，用不了二分
int pos1=-1,pos2=-1;
for(int i=0;i<sizeof(buff);i++)
{
if(0xFF == buff[i])
{
if(-1 == pos1)//起始位置只能初始化一次
{
pos1 = i;
}

pos2 = i;//不停更新结束位置
}
}
//如果数组很大，则可以用状态机来做，略过后面的无用功

3万 · 2018-10-24 08:43

如果确认所有FF都是连续的，则在找到pos1后，在后半段里启动二分查找法

只看该作者 · 2018-10-24 10:00

mohanwei 发表于 2018-10-24 08:43
如果确认所有FF都是连续的，则在找到pos1后，在后半段里启动二分查找法

看来确定第一个0xff是没法用二分法了，有没有什么算法能快速找到第一个0xff？

只看该作者 · 2018-10-24 10:12

mohanwei 发表于 2018-10-24 08:43
如果确认所有FF都是连续的，则在找到pos1后，在后半段里启动二分查找法

假如有且只有一个0xff，能否有算法快速找到它？
求帮忙。

1万 · 2018-10-24 10:17

直接搜索一遍就行了，才1000个，很快的

3万 · 2018-10-24 10:26

datouyuan 发表于 2018-10-24 10:12
假如有且只有一个0xff，能否有算法快速找到它？
求帮忙。

没有

只看该作者 · 2018-10-24 11:38

本帖最后由 datouyuan 于 2018-10-24 11:45 编辑

ayb_ice 发表于 2018-10-24 10:17
直接搜索一遍就行了，才1000个，很快的

我这是简化问题。
数据实际是在25q32中，有2M，用于模拟环形缓存。有效数据是不为0xff的任意数。
当数据快满时，把最早存入数据的整个分区擦除。

假如flash中存储最后写入的位置，会造成这位置频繁擦除改写。所以想用快速寻找的办法来定位。

1万 · 2018-10-24 12:12

前提：采用二分法查找时，数据需是排好序的

二分法排序的思想：假设一个数组是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段中查找；若x大于当前位置值则在数列的后半段中继续查找，直到找到为止；当然要是不存在就返回-1（数组下标不可能为负）。

代码如下：

int Binary_Bearch(int arr[], int sz,int num)
{
int mid = 0;
int left = 0;
int right = sz - 1;
assert(arr);
while (left<=right)
{
mid = (left + right) / 2;
if (num > arr[mid])
{
left = mid + 1;
}
else if (num < arr[mid])
{
right=mid-1;
}
else if (num == arr[mid])
{
return mid;
}
}
return -1;
}

测试函数：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>

int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int sz = sizeof(arr) / sizeof(arr[0]);
int num = 8;
int ret=Binary_Bearch(arr, sz, num);
printf("%d\n", ret);
getchar();
return 0;
}

这里结果肯定就是 7
---------------------
作者：My_heart_
来源：CSDN
原文：https://blog.csdn.net/My_heart_/article/details/51345864
版权声明：本文为博主原创**，转载请附上博文链接！

1万 · 2018-10-24 13:30

datouyuan 发表于 2018-10-24 11:38
我这是简化问题。
数据实际是在25q32中，有2M，用于模拟环形缓存。有效数据是不为0xff的任意数。
当数据快 ...

如果是这样

那也需要先找出第一个出现0xff的地方，后面的再二分

1万 · 2018-10-24 14:04

可以二分法查找 , 但是不能先找头 ,先找中间, 然后再找头和尾
没经典的二分法快, 但比逐个查找速度快.

方法是: 不断分成二段, 直到找到0XFF, 定位出来了, 就知道在哪一个二分段了, 然后已经缩小了很小的范围了. 再来二分找头和尾,
有一个缺点, 就是如果0xff 如果只有一个数据, 找起来会比较慢. 和逐个查找差不多了. 如果0xff越长越容易 .

1万 · 2018-10-24 14:12

datouyuan 发表于 2018-10-24 11:38
我这是简化问题。
数据实际是在25q32中，有2M，用于模拟环形缓存。有效数据是不为0xff的任意数。
当数据快 ...

你是想延长FLASH的寿命?

只看该作者 · 2018-10-24 16:26

楼主应该是查找没使用的Flash区域

只看该作者 · 2018-10-25 08:33

你存数据的时候申请2个变量，一个是数据存入的起始地址，一个是数据存入的结尾地址，通过这2个变量来控制删除早期的数据

只看该作者 · 2018-10-26 18:27

你的实现方法有待转换，先找到是哪一页，然后再找页中的位置，都可以用2B法，没有问题的，我就是那么做的

只看该作者 · 2018-10-30 16:39

datouyuan 发表于 2018-10-30 09:02
谢谢，我现在就是这样做的。用普通查找找到第一个空分区，再在前一分区中使用二分法查找。
比完全不用二分 ...

查每一页最后俩字节判断，快又好

只看该作者 · 2018-11-2 09:56

U32 SearchLeft(rU32 u32StartIndex);
U32 SearchRight(rU32 u32StartIndex);
U32 DichotomyFind(U32 u32LeftIndex,U32 u32RightIndex);
——————————————————————————————————————
DichotomyFind  搜索到第一个0xFF 后返回其 Index 并停止：
使用 SearchLeft 向左搜索 0xFF 边界，并返回0xFF的左边界：
使用 SearchRight 向右搜索 0xFF 边界，并返回0xFF的右边界：

求大神帮我写个二分查找的代码，今天想这个头都懵了。

相关帖子

精华达人奖章

欢快之小溪

缘定三生

技术奇才奖章

技术新星奖章

荣誉元老奖章

坚毅之洋流

十世金身

技术领袖奖章

七世轮回

沉静之湖泊

无冕之王奖章

社区建设奖章

湍急之河流

技术导师奖章