3

我把这个作为面试问题...

已排序的无限数组，并且从某个位置（我们不知道该位置）只有特殊符号“$”才会出现，我们需要在该数组中找到一个元素......

我给出了一个解决方案，例如获取 $ 的第一次出现，然后从 $ 对前一部分进行二进制搜索

找到第一次出现的 $ i 给出了解决方案，例如窗口大小增加 if (i,2i)

我给的代码是

#include<stdio.h>

int first(int *arr,int start,int end,int index)
{
    int mid=(start+end)/2;
    if((mid==start||arr[mid-1] != '$') && arr[mid]=='$')
        return mid;
    if(arr[mid]=='$')
        return first(arr,start,mid-1,index);
    else
    {
        if(arr[end] =='$')
            return first(arr,mid+1,end,index);
        else
            return first(arr,end+1,(1<<index),index+1);
    }
}

int binsearch(int *arr,int end ,int n)
{
    int low,high,mid;
    high=end-1;
    low=0;
    while(low<= high)
    {
        mid=(low+high)/2;
        if(n<arr[mid])
            high=mid-1;
        else if (n >arr[mid])
            low=mid+1;
        else
            return mid;
    }
    return -1;
}

int main()
{
    int arr[20]={1,2,3,4,5,6,7,8,9,10,'$','$','$','$','$','$','$','$','$','$'};
    int i =first(arr,0,2,2);
    printf("first occurance of $ is  %d\n",i);
    int n=20;//n is required element to be found
    if(i==0||arr[i-1]<n)
        printf(" element %d not  found",n);
    else{
        int p=binsearch(arr,i,n);
        if(p  != -1)
            printf("element %d is found at index %d",n,p);
        else
            printf(" element %d not found",n);
    }
    return 0;
}

有没有更好的方法来解决上述问题？

而且我还想知道找到 $ 的第一次出现为什么我们应该只以 2 的幂移动窗口为什么不像 (i,3i) 这样 3

有人可以通过一些关于重复关系的信息..请帮助..

4

3 回答 3

3

对我来说似乎是一个很好的方法。作为一个小的优化，first当您达到任何大于您正在搜索的数字（不仅仅是$）时，您可以停止您的例程。

通过 2 的幂来扩大窗口意味着您将在log_2(n)迭代中找到终点。以 3 倍增长意味着你会在log_3(n)迭代中找到它，它更小。但不是渐近更小，如O(log_2(n)) == O(log_3(n))。而且您的二进制搜索无论如何都会采取log_2(n)措施，因此使first零件更快不会帮助您的大O运行时间。

于 2012-09-21T17:31:42.273 回答
0

迭代格式的第一个函数的有效部分是

private int searchNum(int[] arr, int num, int start, int end) {
    int index = 0;
    boolean found = false;
    for (int i = 0; i < arr.length; i = 1 << index) {
        if (start + i < arr.length) {
            if (arr[start] <= num && arr[start + i] >= num) {
                found = true;
                return bsearch(arr, num, start, start + i);
            } else {
                start = start + i;
            }
        } else {
            return bsearch(arr, num, start, arr.length - 1);
        }
    }
    return 0;
}

这不会让您第一次出现，而是尝试直接查找数字，因为在您的情况下，您甚至在找到 $ 符号之前就丢失了可以找到数字本身的概率。所以最坏情况的复杂性是 O(logn).. 最好的情况是 (1) 之后你将它传递给

private int bsearch(int[] array, int search, int first, int last) {
    int middle = (first + last) / 2;
    while (first <= last) {
        if (array[middle] < search)
            first = middle + 1;
        else if (array[middle] == search) {
            System.out.println(search + " found at location "
                    + (middle + 1) + ".");
            return middle;
        } else
            last = middle - 1;

        middle = (first + last) / 2;
    }
    if (first > last)
        System.out.println(search + " is not present in the list.\n");
    return -1;
}

调用函数

    if ((pos = searchNum(arr, num, 0, 2)) != -1) {
        System.out.println("found @ " + pos);
    } else {
        System.out.println("not found");
    }
于 2015-03-20T10:26:34.117 回答
0

这是python解决方案。

arr = [3,5,7,9,10,90,100,130,140,160,170,171,172,173,174,175,176]
elm = 171
k = 0
while (True):
    try:
        i = (1 << k) - 1 #  same as 2**k - 1 # eg 0,1,3,7,15
        # print k
        if(arr[i] == elm):
            print "found at " + str(i)
            exit()
        elif( arr[i] > elm):
            break                   

    except Exception as e:          
        break
    k = k+1

begin = 2**(k-1) # go back to previous power of 2
end = 2**k -1 

# Binary search
while (begin <= end):
    mid = begin + (end-begin)/2
    try:
        if(arr[mid] == elm):
            print "found at " + str(mid)
            exit()          
        elif(arr[mid] > elm):
            end = mid-1
        else:
            begin = mid+1

    except Exception as e:
        # Exception can occur if you are trying to access min element and that is not available. hence set end to mid-1
        end = mid-1


print "Element not found"
于 2017-05-27T10:49:59.580 回答