Jump-Suchalgorithmus in Python

Question

Ich versuche, die Sprungsuche in Python zu implementieren.

hier ist der Code

''' 
2 jump search 
''' 
import math 
def jump_search(arr,search): 
    interval = int(math.sqrt(len(arr))) 
    for i in range(0,len(arr),interval): 
     if arr[i] > search: 
      chunk = i 
      break 
     if arr[i] == search: 
      return i 
    arr_ls = arr[chunk-interval:chunk] 
    ind = [i for i,d in enumerate(arr_ls) if d==search] 
    return chunk-interval+ind[0] 
arr = [ i for i in range(1,200,15)] 

res = jump_search(arr, 121) 
print(res) 

hier die Probleme, die ich bin vor:

1. letzte Brocken ist das Überspringen
2. Verbesserte Version? Auch ich glaube nicht, mein Code sauber und kurz

Answer 1

Derzeit wenn die search Variable in den letzten Brocken sind, dann wird chunk nicht initialisiert werden. Und daher müssen Sie einen Fehler erhalten. Warum also nicht speziell nach dem letzten Intervall suchen? Ich habe eine flag Variable hinzugefügt, die dafür prüft. Wenn Brocken gefunden wird, gut und gut, sonst müssen wir das letzte Intervall sehen.

import math 
def jump_search(arr,search): 
    flag = 0 
    interval = int(math.sqrt(len(arr))) 
    for i in range(0,len(arr),interval): 
     if arr[i] > search: 
      chunk = i 
      flag = 1 
      break 
     if arr[i] == search: 
      return i 
    if flag==0: 
     c=i 
     for j in arr[i:]: 
      if j==search: 
       return c 
      c+=1 
    else: 
     arr_ls = arr[chunk-interval:chunk] 
     ind = [i for i,d in enumerate(arr_ls) if d==search] 
     return chunk-interval+ind[0] 
arr = [ i for i in range(1,200,15)] 
res = jump_search(arr, 196) 
print(res) 
# prints 13 

Außerdem werden Sie nicht alles tun müssen, wenn Sie den Überblick über die lower bound halten anstelle des upper bound, die Sie jetzt gerade sind. Also machen Sie sich besser codieren, die Sie gefragt, versuchen Sie dies:

import math 
def jump_search(arr,search): 
    low = 0 
    interval = int(math.sqrt(len(arr))) 
    for i in range(0,len(arr),interval): 
     if arr[i] < search: 
      low = i 
     elif arr[i] == search: 
      return i 
     else: 
      break # bigger number is found 
    c=low 
    for j in arr[low:]: 
     if j==search: 
      return c 
     c+=1 
    return "Not found" 

arr = [ i for i in range(1,200,15)] 
res = jump_search(arr, 196) 
print(res) 
# prints 13 

Answer 2

Ihr Code überspringt letzten Brocken, weil Schritt der for-Schleife größer ist als letzte Blocklänge. Auch würde es scheitern, wenn Sie versuchen, Suchelement, das nicht in der Liste ist.

Zusammengefasst - dies sollte für Sie arbeiten:

import math 


def jump_search(arr, search): 
    interval = int(math.sqrt(len(arr))) 
    i = 0 
    # set i to zero if list is empty 
    for i in range(0, len(arr), interval): 
     if arr[i] > search: 
      break 
     if arr[i] == search: 
      return i 
    else: 
     # if loop exited normaly - add interval to i, so last chuck is included too 
     i += interval 

    last_chunk = arr[i - interval:i] 

    # iterate directly and simply break if item found 
    for ind, val in enumerate(last_chunk): 
     if val == search: 
      break 
    else: 
     # if loop exited normaly - item not found in chunk 
     # return None instead of index 
     return None 
    return i - interval + ind