Найти элемент в отсортированном массиве

Учитывая отсортированный массив A и элемент x, мне нужно найти алгоритм, который возвращает индекс x в A или -1 если x не в A. временная сложность алгоритма должна быть Θ(logd), когда d является количество элементов, которое появляется, прежде чем x в A, или если x не в A, д является количество элементов, которые были до x, если он был в A.Найти элемент в отсортированном массиве

Двоичный поиск не достаточно хорош, потому что его лучшим случаем является O (1). Я думал начать с начала массива и начать проверять индексы, обладающие степенями 2. но я потерялся.

источник

2016-11-25 Genadi

Двоичный поиск в худшем случае * is * O (log n) ... –

Если бы это был журнал (размер (A)) 'вы хотели, бинарный поиск работал бы. Если вы пытаетесь оптимизировать с точки зрения местоположения 'x', моя кишка говорит о полномочиях проверки' 2', пока вы не найдете значение больше, чем 'x', а затем двоичный поиск в верхней половине, но я не совершенно ясно, что вы просите. –

@taylorswift Я знаю, но мне нужно 'Θ (logd)', что означает, что лучшим случаем является logd, а его неправильный в двоичном поиске. – Genadi

Вы можете сделать это следующим образом: он использует шаги Θ (log d), чтобы найти диапазон размеров Θ (d), а затем выполняет бинарный поиск в этом диапазоне в других шагах Θ (log d).

int search(int[] array, int length, int valueToFind) 
{ 
    int pos=0; 
    int limit=min(length,1); 
    while(limit < length && array[limit] < valueToFind) 
    { 
     pos=limit+1; 
     limit = min(length, limit*2+1); 
    } 
    while(pos<limit) 
    { 
     int testpos = pos+((limit-pos)>>1); 

     if (array[testpos]<valueToFind) 
      pos=testpos+1; 
     else 
      limit=testpos; 
    } 
    return (pos < length && array[pos]==valueToFind ? pos : -1); 
}

Обратите внимание, что бинарный поиск я использую не выходит рано, и всегда берет Q (журнал (ограничительный Pos)) время. Тем не менее, это быстрее, чем другие поисковые запросы, которые выходят раньше, потому что он выполняет только одно сравнение на итерацию. Я описываю другие преимущества здесь:

How can I simplify this working Binary Search code in C?

источник

2016-11-25 18:01:35

Это хорошо! что означает оператор '>>'? – Genadi

@ Genadi >> 1 означает сдвиг вправо на 1 бит. Это то же самое, что и/2, за исключением того, что деление всегда округляется вниз, а не округляется до 0, т. Е. 5 >> 1 == 2 и -5 >> 1 == -3. Разница не важна в этом приложении - я мог бы написать/2, но я стар, и я помню время, когда была разница в производительности. –

У меня есть простой python реализации, основанной на силе 2's подхода, как описано в разделе комментариев. Пожалуйста, посмотрите:

def binary_search(nums,low,high,x): 
    while low<=high: 
    mid = (low+high)/2 
    if nums[mid]==x: 
     return mid+1 
    elif nums[mid]>x: 
     high = mid-1 
    else: 
     low = mid+1 
    return -1 

def find_index(nums,x): 
    i = 1 
    l = len(nums) 
    while i<l: 
    if nums[i-1]==x: 
     return i 
    elif 2*i<l and nums[2*i-1]>x: 
     return binary_search(nums,i-1,2*i-1,x) 
    i = 2*i 
    return binary_search(nums,i/2,l-1,x) 

def main(): 
    line = raw_input("Enter numbers: ").split() 
    nums = [] 
    for ele in line: 
    nums.append(int(ele)) 

    nums = sorted(nums) 
    print "Sorted array: ",nums 
    x = int(raw_input("Enter the element to find in sorted array: ")) 
    print find_index(nums, x) 

main()

Во-первых, он пытается найти целевой элемент путем перемещения над индексами с мощностью 2.

В любой момент, если текущий элемент превышает целевой элемент, то мы делаем binary search между током индекса (текущей мощностью 2) и предыдущего индексом (предыдущие мощностями 2).

Сложность процесса поиска - logd в среднем. Также наилучшая временная сложность - logd как и ожидалось !!

Надеюсь, что это легко понять !!!!

источник

2016-11-25 18:09:55

Найти элемент в отсортированном массиве

ответ

Смежные вопросы