2

我正在寻找一种算法来找到整数数组中小于 X 的第一个数字。实际上我正在使用线性搜索，但我认为二进制搜索可能更好（正如我前一段时间已经看到的那样）但我不知道如何自己实现它（不实现修改版本来查找第一个小于X）。如果有比 bin 搜索更好的方法，请告诉我。我需要它，因为该数组在程序运行时被大量访问和修改。

这是当前（繁琐）的实现：

int findmin(int *arr,int n,int size)
{
  int i;
  for(i = 0; i < size && arr[i] < n; i++)
    ;
  return i-1;
}

该索引用于在特定索引中插入 N 值的功能的参数输入。此函数的索引并在数组中插入一个数字，但在每次插入新数字时仍使其排序而无需调用 sort()。它是一个相关的文件文本解析，解析很多文件和一些相当多的字符。我需要努力使事情尽可能快（根据我的上下文和知识）。

编辑：数组总是排序的，即使在新数字的分割之后也是如此。

4

2 回答 2

2

二进制搜索在这里没有问题。困难的是如何检查边界条件以及应该返回什么值。此外，您必须注意重复值。以下功能将起作用。

    int binarySearch(int a[], int length, int value)
    {
        if (a[0] > value)
            return -1;

        int low = 0;
        int high = length-1;

        while (low<=high)
        {
            int mid = low+((high-low)/2);

            if(a[mid] >= value)
                high = mid-1;
            else
                low = mid+1;
        }

        return low-1;
    }

测试：（有重复）

    int arr[] = {1, 3, 4, 6, 6, 10};
    int length = sizeof(arr)/sizeof(arr[0]);

    int index = binarySearch(arr, length, 6); // will be 2
于 2013-12-20T13:13:05.073 回答
2

您必须已经对 N 个元素的数组进行了排序。

将“高”设置为 N，将“低”设置为 -1。

“探测”元素 N/2（向下舍入为 int）。

如果探测到的元素<您的目标，请将“高”设置为 N/2。如果 >，将“低”设置为 N/2。（如果 ==，当然，那么你有你的答案。）

重复，在“低”和“高”之间探测。

您需要担心一些边界条件，但不要太复杂。

于 2013-03-19T02:09:05.377 回答