3

面接の質問としてもらった...

ソートされた無限配列（位置はわかりません）からは、特別な記号'$'のみが存在し、その配列内の要素を見つける必要があります...

私は$の最初の出現を取得し、次に$から前の部分で二分探索を行うような解決策を与えました

$の最初の出現を見つけるために、（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ではないのはなぜですか

誰かが再発関係についていくつかの光を通してplsすることができますか..plsは助けます..

4

3 に答える 3

3

私にはそれを行うための良い方法のようです。小さな最適化として、first（だけでなく）探している数よりも大きい数に達したときにルーチンを停止できます$。

log_2(n)2の累乗でウィンドウを拡大するということは、反復で終わりを見つけることを意味します。log_3(n)3倍に成長するということは、それがより小さな反復で見つかることを意味します。しかし、のように漸近的に小さくはありませんO(log_2(n)) == O(log_3(n))。そして、あなたの二分探索はlog_2(n)とにかくステップを踏むでしょう、それでfirst部品をより速くすることはあなたのbig-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 に答える