PythonPython · Chapterبەش 11 · Lectureوانە 11.4

Binary Search and Hashingگەڕانی دووانی و هاشکردن

Searching for a key: a one-screen recap of linear search, binary search on sorted lists with full traces, its $\lfloor \log_2 n \rfloor + 1$ bound and the bisect module, hashing with the remainder method, collisions and linear probing, Python's dict and set as hash tables, and a summary of the whole data-structures chapter.

گەڕان بەدوای : پێداچوونەوەی لە یەک پەڕەدا، لەسەر ڕیزکراو بە بەدواداچوونی تەواو، سنووری $\lfloor \log_2 n \rfloor + 1$ و bisect، هاشکردن بە ڕێگای ، و ، و وەک ، هەروەها پوختەی هەموو بەشی .

29 min read27 خولەک خوێندنەوە · 24 stepsهەنگاو

What you will learnچی فێر دەبیت

Say what searching is and compare linear search, binary search and hashing.
Trace binary search with first, last and mid for a present and a missing key, and write it in Python.
Explain why binary search needs sorted data and needs at most $\lfloor \log_2 n \rfloor + 1$ looks, and use the bisect module.
Build and search a hash table with k % size, and handle collisions with linear probing.
Explain why Python's dict and set are fast and why their keys must be hashable.

بڵێیت گەڕان چییە و ، و هاشکردن بەراورد بکەیت.
بەدواداچوون بۆ بکەیت بە first، last و mid بۆ کە هەیە و یەکێک کە نییە و بە بینووسیت.
ڕوون بکەیتەوە بۆچی ڕیزکراوی پێویستە و لانیزۆر $\lfloor \log_2 n \rfloor + 1$ سەیرکردنی دەوێت و bisect بەکار بهێنیت.
بە k % size دروست بکەیت و تێیدا بگەڕێیت و بە چارەسەر بکەیت.
ڕوون بکەیتەوە بۆچی و خێران و بۆچی دەبێت بن.

What is searching?گەڕان چییە؟

Searching answers two questions about a collection: is a certain value in it, and if so, where? The value we look for is called the key: a student number, a word, a price. This lesson compares three ways to search: linear search, which checks the items one by one; binary search, which needs sorted data and halves the search every time; and hashing, which computes where the key must be.

گەڕان وەڵامی دوو پرسیار دەداتەوە دەربارەی کۆمەڵێک : ئایا دیاریکراو تێیدایە و ئەگەر هەیە، لە کوێیە؟ ئەو بەدوایدا دەگەڕێین پێی دەوترێت : ژمارەی قوتابییەک، وشەیەک، قیمەتێک. ئەم وانەیە سێ ڕێگای گەڕان بەراورد دەکات: کە یەک یەک دەپشکنێت؛ کە ڕیزکراوی پێویستە و هەموو جارێک گەڕانەکە نیوە دەکات؛ و هاشکردن کە دەژمێرێت دەبێت لە کوێ بێت.

Quick checkپشکنینی خێراA school wants to know whether student number 2041 is in its list of 900 students, and at which position. What is 2041 in this search?قوتابخانەیەک دەیەوێت بزانێت ئایا ژمارەی قوتابی ⁦2041⁩ لە ⁦900⁩ قوتابییەکەیدا هەیە و لە چ شوێنێکدایە. لەم گەڕانەدا ⁦2041⁩ چییە؟The keyکلیلەکەThe list sizeقەبارەی لیستەکەThe indexئیندێکسەکە

Linear search in one screenگەڕانی هێڵی لە یەک پەڕەدا

You already know linear search. Python's in and index() compare the key with the items one by one from index 0 and stop at the first match (How in searches, index()); index() raises a ValueError when the key is missing (When the value is missing); and a loop with break does the same by hand (break to stop a search). Linear search works on any list, sorted or not. Its cost:

پێشتر دەناسیت. in و index()ـی لەگەڵ یەک یەک لە 0ـەوە بەراورد دەکەن و لە یەکەم یەکسانیدا دەوەستن (in چۆن دەگەڕێت، ⁦index()⁩)؛ index() کاتێک نییە ValueError دەدات (کاتێک نرخەکە نییە)؛ و بە break هەمان کار بە دەست دەکات (break بۆ وەستاندنی گەڕان). لەسەر هەر کار دەکات، ڕیزکراو بێت یان نا. تێچووەکەی:

Caseبار	Comparisons for $n$ itemsبەراورد بۆ $n$
best case: the key is the first item: یەکەم	1
worst case: the key is the last item, or missing: دوایین ، یان نییە	$n$
average for a key that is presentتێکڕا بۆ کە هەیە	about $n/2$ نزیکەی $n/2$
the key appears twice دوو جار هەیە	stops at the first oneلە یەکەمیان دەوەستێت

So a missing key in a million items costs a million comparisons. That is fine for small or unsorted lists. For big sorted lists there is a much faster way.

کەواتە کە نییە لە ملیۆنێک ملیۆنێک بەراورد دەخایەنێت. ئەمە بۆ بچووک یان ڕیزنەکراو باشە. بۆ گەورەی ڕیزکراو ڕێگایەکی زۆر خێراتر هەیە.

Binary search: always look in the middleگەڕانی دووانی: هەمیشە سەیری ناوەڕاست بکە

Play "guess my number": I think of a number from 1 to 100, and after each guess I say too small, too big or correct. The clever player always guesses the middle of what is still possible. Too small throws away the lower half at once; too big throws away the upper half. Looking up a word in a paper dictionary or a name in a phone book works the same way: you open near the middle and keep only the half that can hold the word.

یاری «ژمارەکەم بدۆزەرەوە» بکە: من بیر لە ژمارەیەک لە 1 تا ⁦100⁩ دەکەمەوە و دوای هەر هەوڵێک دەڵێم بچووکە، گەورەیە یان ڕاستە. یاریزانی زیرەک هەمیشە ناوەڕاستی ئەوەی هێشتا دەگونجێت هەڵدەبژێرێت. بچووکە یەکسەر نیوەی خوارەوە فڕێ دەدات؛ گەورەیە نیوەی سەرەوە. گەڕان بەدوای وشەیەکدا لە فەرهەنگێکی کاغەزیدا یان ناوێک لە دەفتەری تەلەفۆندا بە هەمان شێوە کار دەکات: نزیک ناوەڕاست دەیکەیتەوە و تەنها ئەو نیوەیە دەهێڵیتەوە کە دەشێت وشەکەی تێدا بێت.

The computer plays "guess my number"کۆمپیوتەر یاری «ژمارەکەم بدۆزەرەوە» دەکاتguess_game.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

secret = 73
low, high = 1, 100
guesses = 0
while True:
    guess = (low + high) // 2             # always guess the middle
    guesses += 1
    if guess == secret:
        print(f"guess {guesses}: {guess} - correct!")
        break
    elif guess < secret:
        print(f"guess {guesses}: {guess} - too small")
        low = guess + 1
    else:
        print(f"guess {guesses}: {guess} - too big")
        high = guess - 1

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 5

Always guess the middle of what is still possible.

هەمیشە ناوەڕاستی ئەوەی هێشتا دەگونجێت هەڵبژێرە.

Lineدێڕی 12

Too small: the secret is above the guess.

بچووکە: ژمارە نهێنییەکە لە سەرووی هەوڵەکەوەیە.

Binary search does this on a sorted list. Compare the key with the middle item. There are three possibilities: they are equal, and the search is over; the key is smaller, so it can only be in the left half; or the key is bigger, so it can only be in the right half. Repeat on the half that is left, until the key is found or nothing is left.

ئەمە لەسەر ڕیزکراو دەکات. لەگەڵ ناوەڕاست بەراورد بکە. سێ ئەگەر هەیە: یەکسانن و گەڕانەکە تەواو بووە؛ بچووکترە، بۆیە تەنها دەتوانێت لە نیوەی چەپدا بێت؛ یان گەورەترە، بۆیە تەنها دەتوانێت لە نیوەی ڕاستدا بێت. لەسەر ئەو نیوەیەی دەمێنێتەوە دووبارەی بکەرەوە، تا دەدۆزرێتەوە یان هیچ نامێنێت.

Definitionپێناسە

A way to find a value in a sorted list: look at the middle item, throw away the half that cannot contain the value, and repeat. A list of n items needs at most $\lfloor\log_2 n\rfloor+1$ looks.

ڕێگایەک بۆ دۆزینەوەی بەهایەک لە لیستێکی ڕیزکراودا: سەیری دانەی ناوەڕاست دەکەیت، ئەو نیوەیەی کە بەهاکەی تێدا نییە فڕێ دەدەیت و هەمان کار دووبارە دەکەیتەوە. لیستێکی n دانەیی لانیزۆر $\lfloor\log_2 n\rfloor+1$ سەیرکردنی پێویستە.

Quick checkپشکنینی خێراA sorted list is searched for a key. The middle item is bigger than the key. What happens next?بەدوای لە ڕیزکراودا دەگەڕێین. ناوەڕاست لە گەورەترە. دواتر چی ڕوو دەدات؟The right half is dropped; the search goes on in the left halfنیوەی ڕاست فڕێ دەدرێت؛ گەڕان لە نیوەی چەپدا بەردەوام دەبێتThe left half is droppedنیوەی چەپ فڕێ دەدرێتThe key is not in the listکلیلەکە لە لیستەکەدا نییە

Binary search in 4 minutesMichael Sambol · Englishئینگلیزی · 254K viewsبینین · 4.8K likesلایک
Binary search on a sorted list: look in the middle, keep one half, repeat; the loop in code and why it needs about log n steps.
لەسەر ڕیزکراو: سەیری ناوەڕاست بکە، نیوەیەک بهێڵەرەوە و دووبارەی بکەرەوە؛ لە کۆددا و بۆچی نزیکەی $\log n$ هەنگاوی پێویستە.
Whole video (4:00): an example (0:00), the algorithm (1:58) and its time complexity (2:51).
هەموو ڤیدیۆکە ⁦(4:00)⁩: نموونەیەک ⁦(0:00)⁩، ⁦(1:58)⁩ و ⁦(2:51)⁩.

Binary search: always look in the middleگەڕانی دووانی: هەمیشە سەیری ناوەڕاست بکە

The algorithm step by stepئەلگۆریزمەکە هەنگاو بە هەنگاو

Binary search in plain stepsگەڕانی دووانی بە هەنگاوی سادە

Set first = 0 and last = n - 1: at the start the whole list may hold the key.
first = 0 و last = n - 1 دابنێ: لە سەرەتادا هەموو لەوانەیە تێدا بێت.
While first <= last, there is still a part to search: compute mid = (first + last) // 2, the middle index rounded down (floor division).
تا first <= last بێت، هێشتا بەشێک بۆ گەڕان هەیە: mid = (first + last) // 2 بژمێرە، ناوەڕاست بە نزیککردنەوە بۆ خوارەوە (دابەشکردنی بەرەو خوار).
If values[mid] equals the key, the search succeeds: return mid.
ئەگەر values[mid] یەکسان بوو بە ، گەڕانەکە سەرکەوتووە: mid بگەڕێنەوە.
If the key is smaller than values[mid], keep the left half: last = mid - 1. Otherwise keep the right half: first = mid + 1.
ئەگەر لە values[mid] بچووکتر بوو، نیوەی چەپ بهێڵەوە: last = mid - 1. ئەگەرنا نیوەی ڕاست بهێڵەوە: first = mid + 1.
When first > last, no part is left: the key is not in the list (return -1).
کاتێک first > last بوو، هیچ بەشێک بۆ گەڕان نییە: لە نییە (return -1).

Binary search: always look in the middleگەڕانی دووانی: هەمیشە سەیری ناوەڕاست بکە

Trace 1: the key is in the listبەدواداچوونی یەکەم: کلیلەکە لە لیستەکەدا هەیە

Fifteen bus tickets were sold for a trip from Erbil to Duhok, and their numbers are kept sorted: [3, 8, 11, 15, 21, 26, 30, 34, 42, 47, 53, 58, 64, 71, 79]. Is ticket 64 among them?

پازدە بلیتی پاس بۆ گەشتێک لە هەولێرەوە بۆ دهۆک فرۆشراون و ژمارەکانیان بە ڕیزکراوی هەڵگیراون: [3, 8, 11, 15, 21, 26, 30, 34, 42, 47, 53, 58, 64, 71, 79]. ئایا بلیتی ⁦64⁩ لە ناویاندایە؟

Four rounds. A linear search would have needed 13 comparisons.چوار هەنگاو. پێویستی بە ⁦13⁩ بەراورد دەبوو.
Roundهەنگاو	first	last	mid	values[mid]	Compareبەراورد	Nextدواتر
1	0	14	7	34	`34 < 64`	`first = 8`
2	8	14	11	58	`58 < 64`	`first = 12`
3	12	14	13	71	`71 > 64`	`last = 12`
4	12	12	12	64	`64 == 64`	found: `return 12`دۆزرایەوە: `return 12`

Fifteen sorted numbers in boxes with their indexes 0 to 14, and the pointers first, mid and last. Searching for 64: the middle box 34 is smaller, so boxes 0 to 7 turn grey; the middle 58 is smaller, so boxes up to 11 turn grey; the middle 71 is bigger, so boxes 13 and 14 turn grey; the box 64 at index 12 is found and turns green after four looks. Then searching for 40: after two steps only 42, 47 and 53 are left; 47 is bigger, then 42 is bigger; first becomes 8 and last 7, nothing is left, and the function returns −1. — Each look throws away half of what is still possible: $15 \to 7 \to 3 \to 1$ .هەر سەیرکردنێک نیوەی ئەو بەشەی هێشتا دەگونجێت فڕێ دەدات: $15 \to 7 \to 3 \to 1$ .CêIT

Binary search: always look in the middleگەڕانی دووانی: هەمیشە سەیری ناوەڕاست بکە

Trace 2: the key is missingبەدواداچوونی دووەم: کلیلەکە نییە

Now look for ticket 40, which was never sold. Binary search cannot see that at once; it keeps halving until nothing is left: first becomes bigger than last.

ئێستا بەدوای بلیتی ⁦40⁩دا بگەڕێ کە هەرگیز نەفرۆشراوە. ناتوانێت یەکسەر ئەوە ببینێت؛ بەردەوام نیوە دەکات تا هیچ نامێنێت: first لە last گەورەتر دەبێت.

Four rounds to be sure that 40 is not there; a linear search would compare all 15 tickets.چوار هەنگاو بۆ دڵنیابوون لەوەی ⁦40⁩ نییە؛ هەموو ⁦15⁩ بلیتەکە بەراورد دەکات.
Roundهەنگاو	first	last	mid	values[mid]	Compareبەراورد	Nextدواتر
1	0	14	7	34	`34 < 40`	`first = 8`
2	8	14	11	58	`58 > 40`	`last = 10`
3	8	10	9	47	`47 > 40`	`last = 8`
4	8	8	8	42	`42 > 40`	`last = 7`
endکۆتایی	8	7	—	—	`first > last`	not found: `return -1`نەدۆزرایەوە: `return -1`

Each comparison that does not find the key still teaches us something: whether the key would lie before or after the middle. That is why every round removes about half of the part that is left.

هەر بەراوردێک کە نادۆزێتەوە هێشتا شتێکمان فێر دەکات: ئایا لە پێش ناوەڕاستەوە دەبوو یان لە دوای. هەر بۆیە هەر هەنگاوێک نزیکەی نیوەی ئەو بەشەی هێشتا دەگونجێت لادەبات.

Quick checkپشکنینی خێراWhy does the search stop when first is 8 and last is 7?بۆچی گەڕانەکە دەوەستێت کاتێک first 8ـە و last 7ـە؟The part between first and last is empty, so the key is not in the listبەشی نێوان first و last بەتاڵە، بۆیە کلیلەکە لە لیستەکەدا نییەIndex 7 holds 34, which is smaller than 40لە ئیندێکسی 7دا ⁦34⁩ هەیە، کە لە ⁦40⁩ بچووکترەBinary search always stops after four roundsگەڕانی دووانی هەمیشە دوای چوار هەنگاو دەوەستێت

Binary search in Pythonگەڕانی دووانی لە Pythonـدا

The steps become a function that returns the index of the key, or $-1$ when the key is missing. A search only returns positions 0 to $n-1$ , so $-1$ clearly means "not found". Test for it before you use the result: in Python values[-1] is still a valid index (the last item).

هەنگاوەکان دەبنە کە دەگەڕێنێتەوە، یان $-1$ کاتێک نییە. گەڕان تەنها شوێنەکانی 0 تا $n-1$ دەگەڕێنێتەوە، بۆیە $-1$ بە ڕوونی واتای «نەدۆزرایەوە»یە. پێش بەکارهێنانی ئەنجامەکە بیپشکنە: لە values[-1] هێشتا دروستە (دوایین ).

A binary search functionکردارێکی گەڕانی دووانیbinary_search.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

def binary_search(values, key):
    """Return the index of key in the sorted list values, or -1."""
    first = 0
    last = len(values) - 1
    while first <= last:                  # some part is still left to search
        mid = (first + last) // 2         # the middle of that part
        if values[mid] == key:
            return mid                    # found
        elif key < values[mid]:
            last = mid - 1                # keep the left half
        else:
            first = mid + 1               # keep the right half
    return -1                             # first > last: nothing left, not found


tickets = [3, 8, 11, 15, 21, 26, 30, 34, 42, 47, 53, 58, 64, 71, 79]
print(binary_search(tickets, 64))
print(binary_search(tickets, 40))

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 5

<=: a part with one item (first == last) must still be checked.

<=: بەشێک بە یەک (first == last) هێشتا دەبێت بپشکنرێت.

Lineدێڕی 6

// keeps the index a whole number.

// بە دەهێڵێتەوە.

Lineدێڕی 10, 12

mid - 1 and mid + 1: the middle item is already checked, so it is left out.

mid - 1 و mid + 1: ناوەڕاست پێشتر پشکنراوە، بۆیە لادەبرێت.

Binary search in Pythonگەڕانی دووانی لە Pythonـدا

Reading the list, and counting roundsخوێندنەوەی لیست و ژماردنی هەنگاوەکان

A version that reads the list and the key from the keyboard. The numbers are typed on one line and split into a list (splitting text):

وەشانێک کە و لە دەخوێنێتەوە. ژمارەکان لە یەک دێڕدا دەنووسرێن و دابەش دەکرێن بۆ (دابەشکردنی دەق):

Search in numbers typed by the userگەڕان لەو ژمارانەی بەکارهێنەر دەینووسێتbinary_input.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

def binary_search(values, key):
    first, last = 0, len(values) - 1
    while first <= last:
        mid = (first + last) // 2
        if values[mid] == key:
            return mid
        elif key < values[mid]:
            last = mid - 1
        else:
            first = mid + 1
    return -1


text = input("Numbers in ascending order, separated by spaces: ")
numbers = [int(part) for part in text.split()]
key = int(input("Number to find: "))
position = binary_search(numbers, key)
if position == -1:
    print(key, "is not in the list")
else:
    print(key, "is at index", position, "(place", position + 1, "in the list)")

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 15

One int per typed number.

بۆ هەر ژمارەیەکی نووسراو یەک int.

Lineدێڕی 21

Index 4 is the 5th place: people count from 1, Python from 0.

4 شوێنی پێنجەمە: خەڵک لە 1ـەوە دەژمێرن، لە 0ـەوە.

How many rounds does each key need? The function below counts them for some tickets:

هەر پێویستی بە چەند هەنگاو هەیە؟ ئەم خوارەوە بۆ چەند بلیتێک دەیانژمێرێت:

Rounds for several keysهەنگاوەکان بۆ چەند کلیلێکrounds_table.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

def rounds_needed(values, key):
    first, last = 0, len(values) - 1
    rounds = 0
    while first <= last:
        mid = (first + last) // 2
        rounds += 1
        if values[mid] == key:
            return rounds, "found"
        elif key < values[mid]:
            last = mid - 1
        else:
            first = mid + 1
    return rounds, "not found"


tickets = [3, 8, 11, 15, 21, 26, 30, 34, 42, 47, 53, 58, 64, 71, 79]
for key in [34, 58, 47, 64, 3, 40, 80]:
    print(key, rounds_needed(tickets, key))

34 sits exactly in the middle and is found in one round. No key, present or missing, needs more than 4 rounds for these 15 tickets.

⁦34⁩ ڕێک لە ناوەڕاستدایە و لە یەک هەنگاودا دەدۆزرێتەوە. هیچ ، هەبێت یان نەبێت، بۆ ئەم ⁦15⁩ بلیتە لە 4 هەنگاو زیاتری ناوێت.

Unsorted lists and largest-first listsلیستێکی ڕیزنەکراو و گەورەترین لە سەرەتادا

What if the list is not sorted? Binary search does not check, and Python gives no error. It simply throws away halves that may hold the key, so the answer is sometimes right by luck and sometimes wrong:

ئەگەر ڕیزنەکراو بێت چی دەبێت؟ ناپشکنێت و هیچ نادات. تەنها ئەو نیوانە فڕێ دەدات کە لەوانەیە تێیاندا بێت، بۆیە وەڵامەکە جاری وایە بە بەخت ڕاستە و جاری وایە هەڵەیە:

Binary search on an unsorted listگەڕانی دووانی لەسەر لیستێکی ڕیزنەکراوunsorted.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

def binary_search(values, key):
    first, last = 0, len(values) - 1
    while first <= last:
        mid = (first + last) // 2
        if values[mid] == key:
            return mid
        elif key < values[mid]:
            last = mid - 1
        else:
            first = mid + 1
    return -1


prices = [750, 250, 1500, 500, 2000, 1000, 3000]      # NOT sorted (IQD)
print(binary_search(prices, 1000))     # 1000 is at index 5: found, by luck
print(binary_search(prices, 750))      # 750 IS in the list, at index 0
print(binary_search(sorted(prices), 750))

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 16

750 is at index 0, but the first middle is 500, so the left half (with 750) is thrown away.

⁦750⁩ لە 0دایە، بەڵام یەکەم ناوەڕاست ⁦500⁩ـە، بۆیە نیوەی چەپ (کە ⁦750⁩ی تێدایە) فڕێ دەدرێت.

Lineدێڕی 17

Sorted first, the same search finds 750 at index 2 of the sorted list.

دوای ، هەمان گەڕان ⁦750⁩ لە 2ی ڕیزکراودا دەدۆزێتەوە.

If the list is sorted largest first, binary search still works with one change: bigger values are now on the left, so when the key is bigger than the middle item, keep the left half.

ئەگەر بە گەورەترین لە سەرەتادا ڕیزکرابێت، بە یەک گۆڕانکاری هێشتا کار دەکات: ئێستا گەورەترەکان لە چەپن، بۆیە کاتێک لە ناوەڕاست گەورەتر بوو، نیوەی چەپ بهێڵەوە.

Binary search on a largest-first listگەڕانی دووانی لەسەر لیستێک بە گەورەترین لە سەرەتاداbinary_descending.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

def binary_search_desc(values, key):
    """values is sorted from largest to smallest."""
    first, last = 0, len(values) - 1
    while first <= last:
        mid = (first + last) // 2
        if values[mid] == key:
            return mid
        elif key > values[mid]:           # the only change: > instead of <
            last = mid - 1                # bigger values are on the LEFT now
        else:
            first = mid + 1
    return -1


scores = [98, 91, 85, 77, 70, 64, 52, 40]
print(binary_search_desc(scores, 77))
print(binary_search_desc(scores, 60))

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 8

> instead of <.

> لەبری <.

Quick checkپشکنینی خێراYou run binary search on an unsorted list. What can happen? لەسەر ڕیزنەکراو کار پێ دەکەیت. چی ڕوو دەدات؟It sorts the list firstسەرەتا لیستەکە ڕیز دەکاتIt may report that a value is missing although it is thereلەوانەیە ڕابگەیەنێت کە نرخێک نییە لە کاتێکدا هەیەPython raises an errorPython هەڵەیەک دەدات

How many steps? Logarithmic timeچەند هەنگاو؟ کاتی لۆگاریتمی

Every round of binary search halves the part that is still possible. Fifteen tickets become 7, then 3, then 1, so 4 looks are always enough. In general a sorted list of $n$ items needs at most this many looks:

هەر هەنگاوێکی ئەو بەشەی هێشتا دەگونجێت نیوە دەکات. پازدە بلیت دەبنە 7، پاشان 3، پاشان 1، بۆیە 4 سەیرکردن هەمیشە بەسە. بە گشتی ڕیزکراو بە $n$ لانیزۆر پێویستی بەم ژمارەیە سەیرکردن هەیە:

\lfloor \log_2 n \rfloor + 1

Halving again and again: the number of looks grows by one each time the list doubles.نیوەکردن بە دووبارە: هەر جارێک دوو هێندە ببێت، ژمارەی سەیرکردنەکان یەک زیاد دەکات.CêIT

This growth has a name: logarithmic time, written $O(\log n)$ . It joins the three speeds of the sorting lesson:

ئەم گەشەیە ناوێکی هەیە: ، وەک $O(\log n)$ دەنووسرێت. دەچێتە پاڵ سێ خێراییەکەی وانەی ڕیزکردن:

Steps for $n$ items. The logarithmic column is the binary-search bound $\lfloor \log_2 n \rfloor + 1$ .هەنگاو بۆ $n$ . ستوونی سنووری : $\lfloor \log_2 n \rfloor + 1$ .
$n$ قەبارە ( $n$ )	constant	logarithmic	linear	quadratic
10	1	4	10	100
1,000	1	10	1,000	1,000,000
1,000,000	1	20	1,000,000	1,000,000,000,000
1,000,000,000	1	30	1,000,000,000	$10^{18}$

Quick checkپشکنینی خێراA sorted list grows from 1,000 to 2,000 items. How many more looks can binary search need, at most? ڕیزکراو لە ⁦1000⁩ دەبێتە ⁦2000⁩. لانیزۆر چەند سەیرکردنی زیاتری پێویست دەبێت؟One moreیەکی زیاتر1,000 more⁦1000⁩ زیاترTwice as manyدوو هێندە

How many steps? Logarithmic timeچەند هەنگاو؟ کاتی لۆگاریتمی

The $2^{30}$ questionپرسیاری $2^{30}$

A sorted database holds $2^{30} = 1\,073\,741\,824$ records. How many comparisons does each search need?

ڕیزکراو $2^{30} = 1\,073\,741\,824$ هەڵدەگرێت. هەر گەڕانێک چەند بەراوردی پێویستە؟

Linear search against binary search on

2^{30}

recordsگەڕانی هێڵی بەرامبەر گەڕانی دووانی لەسەر

2^{30}

تۆمارbig_database.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

import math

n = 2 ** 30
print(f"records: {n:,}")
print(f"linear search, key at the end or missing: {n:,} comparisons")
print(f"linear search, on average: about {(n + 1) // 2:,} comparisons")
print(f"binary search, at most: {math.floor(math.log2(n)) + 1} comparisons")
middle = (0 + n - 1) // 2
print(f"the middle record is at index {middle:,}:")
print(f"  linear search needs {middle + 1:,} comparisons, binary search needs 1")

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 6

On average a present key is found halfway: about $2^{29}$ comparisons.

بە تێکڕا کە هەیە لە نیوەی ڕێگادا دەدۆزرێتەوە: نزیکەی $2^{29}$ بەراورد.

Lineدێڕی 7

At most $\lfloor \log_2 2^{30} \rfloor + 1 = 31$ .

لانیزۆر $\lfloor \log_2 2^{30} \rfloor + 1 = 31$ .

Lineدێڕی 8

The first middle index binary search looks at.

یەکەم ناوەڕاست کە سەیری دەکات.

Linear search needs about half a billion comparisons on average, and binary search at most 31. If the record we want is exactly the middle one, binary search finds it with its very first comparison, while linear search must walk through more than 536 million records to reach it.

بە تێکڕا نزیکەی نیو ملیار بەراوردی دەوێت و لانیزۆر ⁦31⁩. ئەگەر ئەو دەمانەوێت ڕێک ناوەڕاستەکە بێت، بە یەکەم بەراوردی دەیدۆزێتەوە، لە کاتێکدا دەبێت بە زیاتر لە ⁦536⁩ ملیۆن بڕوات تا پێی بگات.

Where binary search is usedگەڕانی دووانی لە کوێ بەکار دێت؟

Binary search, or an idea built on it, is everywhere that data is kept sorted:

، یان بیرۆکەیەک کە لەسەری دروست کراوە، لە هەموو شوێنێکدا هەیە کە بە ڕیزکراوی هەڵدەگیرێت:

Paper dictionaries and phone books: open near the middle, keep the half that holds the word.
Sorted data in programs: the smallest and the largest value are simply the first and the last item, and any value is found in about $\log_2 n$ looks.
Database indexes keep values sorted so that the database can jump to the right rows instead of reading the whole table (Choosing indexes).
Debugging by halving: when a program worked a hundred changes ago and is broken now, test the change in the middle, then the middle of the bad half, and so on. Git automates this with git bisect, which finds the commit that broke the code.

فەرهەنگی کاغەزی و دەفتەری تەلەفۆن: نزیک ناوەڕاست بیکەرەوە، ئەو نیوەیە بهێڵەوە کە وشەکەی تێدایە.
ڕیزکراو لە : بچووکترین و گەورەترین بە سادەیی یەکەم و دوایین و هەر لە نزیکەی $\log_2 n$ سەیرکردندا دەدۆزرێتەوە.
بە ڕیزکراوی دەهێڵنەوە بۆ ئەوەی ڕاستەوخۆ بچێتە سەر لەبری خوێندنەوەی هەموو (هەڵبژاردنی پێڕستەکان).
بە نیوەکردن: کاتێک سەد گۆڕانکاری پێش ئێستا کاری دەکرد و ئێستا شکاوە، گۆڕانکاریی ناوەڕاست تاقی بکەرەوە، پاشان ناوەڕاستی نیوە خراپەکە و بەم شێوەیە. Git ئەمە بە git bisect خۆکار دەکات، کە ئەو دەدۆزێتەوە کە کۆدەکەی شکاند.

Quick checkپشکنینی خێراA program worked 64 commits ago and is broken now. With debugging by halving, about how many versions must you test to find the commit that broke it? ⁦64⁩ پێش ئێستا کاری دەکرد و ئێستا شکاوە. بە بە نیوەکردن، نزیکەی چەند وەشان دەبێت تاقی بکەیتەوە تا ئەو بدۆزیتەوە کە شکاندی؟About 6نزیکەی 6All 64هەموو ⁦64⁩About 32نزیکەی ⁦32⁩

Python's bisect moduleمۆدیوڵی `bisect`ـی Python

Python has binary search built in, in the bisect module (importing modules). bisect_left(values, key) returns the position where key is, or where it would have to be inserted to keep the list sorted, so a test of that one position tells you whether the key is present. insort(values, key) inserts a value at its sorted place, like the names program in the sorting lesson. The list must already be sorted.

تێدایە، لە bisect (هاوردەکردنی مۆدیوڵەکان). bisect_left(values, key) ئەو شوێنە دەگەڕێنێتەوە کە keyـی تێدایە، یان ئەو شوێنەی دەبێت تێیدا دابنرێت بۆ ئەوەی ڕیزکراو بمێنێتەوە، بۆیە تاقیکردنەوەی ئەو یەک شوێنە پێت دەڵێت ئایا هەیە. insort(values, key) لە شوێنی ڕیزکراوی خۆیدا دادەنێت، وەک ناوەکان لە وانەی ڕیزکردن. دەبێت پێشتر ڕیزکرابێت.

Binary search with the bisect moduleگەڕانی دووانی بە مۆدیوڵی bisectbisect_demo.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

import bisect

tickets = [3, 8, 11, 15, 21, 26, 30, 34, 42, 47, 53, 58, 64, 71, 79]
i = bisect.bisect_left(tickets, 64)
print(i, i < len(tickets) and tickets[i] == 64)      # found?
i = bisect.bisect_left(tickets, 40)
print(i, i < len(tickets) and tickets[i] == 40)      # 40 would go at index 8

names = ["Aram", "Dilan", "Rezan", "Shilan"]
bisect.insort(names, "Karwan")                       # insert in sorted order
print(names)

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 4-5

64 is at index 12: found.

⁦64⁩ لە ⁦12⁩دایە: دۆزرایەوە.

Lineدێڕی 6-7

40 is missing; it would go at index 8, where 42 is now.

⁦40⁩ نییە؛ دەبوو لە 8دا دابنرێت، کە ئێستا ⁦42⁩ی تێدایە.

Lineدێڕی 10

insort searches in about $\log_2 n$ steps, but inserting still shifts the later items.

insort لە نزیکەی $\log_2 n$ هەنگاودا دەگەڕێت، بەڵام دانانەکە هێشتا دواتر دەجووڵێنێت.

Quick checkپشکنینی خێراbisect.bisect_left([10, 20, 30, 40], 25) returns 2. What does that mean?bisect.bisect_left([10, 20, 30, 40], 25) 2 دەگەڕێنێتەوە. واتای چییە؟25 is at index 2⁦25⁩ لە ئیندێکسی 2دایە25 was found after 2 comparisons⁦25⁩ دوای 2 بەراورد دۆزرایەوە25 is not in the list; it would belong at index 2⁦25⁩ لە لیستەکەدا نییە؛ جێگەکەی ئیندێکسی 2 دەبوو

Hashing: compute where the key isهاشکردن: شوێنی کلیلەکە بژمێرە

Linear search looks at items one by one, binary search halves the list. Hashing does better still: a formula, the hash function, turns the key straight into a slot number in a hash table, so one look at that slot answers the question. It is like a cloakroom at a wedding hall: your ticket number tells the attendant exactly which hook holds your coat.

سەیری دەکات یەک یەک، نیوە دەکات. هاشکردن لەوەش باشتر دەکات: فۆرمولەیەک، ، ڕاستەوخۆ دەگۆڕێت بۆ ژمارەی شوێنێک لە ، بۆیە یەک سەیرکردنی ئەو شوێنە وەڵامی پرسیارەکە دەداتەوە. وەک شوێنی هەڵواسینی پاڵتۆ وایە لە هۆڵی ئاهەنگدا: ژمارەی پسوولەکەت ڕێک بە کارمەندەکە دەڵێت پاڵتۆکەت لە کام قولاپدایە.

Definitionپێناسە

A that keeps its items in numbered slots and uses a to compute the slot of each key, so a search usually needs only one look. Python's and are hash tables.

کە لە شوێنی ژمارەداردا هەڵدەگرێت و بەکار دەهێنێت بۆ دیاریکردنی شوێنی هەر ، بۆیە گەڕان زۆرجار تەنها یەک سەیرکردنی پێویستە. و .

A simple hash function for whole numbers is the remainder method: h(k) = k % size, where size is the number of slots (what the remainder is good for). A table of 10 slots uses k % 10, which is just the last digit. Store seven student numbers, 27, 63, 4, 18, 91, 55, 30, each in slot k % 10:

سادە بۆ ڕێگای : h(k) = k % size، کە size ژمارەی شوێنەکانە (پاشماوە بۆ چی باشە). بە ⁦10⁩ شوێن k % 10 بەکار دەهێنێت، کە تەنها دوایین ژمارەیە. حەوت ژمارەی قوتابی، 27, 63, 4, 18, 91, 55, 30، هەڵبگرە، هەر یەکەیان لە شوێنی k % 10:

`27 % 10 = 7`, `63 % 10 = 3`, `4 % 10 = 4`, `18 % 10 = 8`, `91 % 10 = 1`, `55 % 10 = 5`, `30 % 10 = 0`.`27 % 10 = 7`، `63 % 10 = 3`، `4 % 10 = 4`، `18 % 10 = 8`، `91 % 10 = 1`، `55 % 10 = 5`، `30 % 10 = 0`.
Slotشوێن	0	1	2	3	4	5	6	7	8	9
Key	30	91	None	63	4	55	None	27	18	None

Hash Tables and Hash FunctionsComputer Science Lessons · Englishئینگلیزی · 1.8M viewsبینین · 47K likesلایک · Partبەشی 0:00–7:42 (ofلە 13:53)
A hash function turns a key into a slot number with the remainder; collisions and linear probing put the key in the next free slot.
بە دەکاتە ژمارەی شوێنێک؛ کاتێک ڕوودەدات، دەخاتە شوێنی بەتاڵی دواتر.
Watch 0:00–7:42: hash indexes with the remainder (1:18), key-value pairs (2:50), collisions (4:47) and linear probing (6:38).
لە ⁦0:00⁩ تا ⁦7:42⁩ سەیر بکە: هاش بە ⁦(1:18)⁩، ⁦(2:50)⁩، ⁦(4:47)⁩ و ⁦(6:38)⁩.

Hashing: compute where the key isهاشکردن: شوێنی کلیلەکە بژمێرە

A hash table in Pythonخشتەیەکی هاش لە Pythonـدا

The table is a Python list of Nones, one per slot. Storing a key and searching for it both start by computing its slot:

خشتەکە کە بۆ هەر شوێنێک Noneـێکی تێدایە. هەڵگرتنی و گەڕان بەدوایدا هەردووکیان بە ژماردنی شوێنەکەی دەست پێ دەکەن:

A hash table in a Python listخشتەیەکی هاش لە لیستێکی Pythonـداhash_table.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

SIZE = 10
table = [None] * SIZE                     # 10 empty slots: index 0 to 9


def h(key):
    return key % SIZE                     # the remainder method


for key in [27, 63, 4, 18, 91, 55, 30]:
    table[h(key)] = key                   # each key goes straight to its slot
print(table)


def hash_find(key):
    slot = h(key)
    if table[slot] == key:                # one look is enough
        return slot
    return -1


print(hash_find(55), hash_find(41))

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 2

[None] * SIZE makes 10 empty slots.

[None] * SIZE ⁦10⁩ شوێنی بەتاڵ دروست دەکات.

Lineدێڕی 6

The hash function: the remainder method.

: ڕێگای .

Lineدێڕی 14-18

Searching costs one look, however big the table is.

گەڕان یەک سەیرکردن دەخایەنێت، هەر چەندە گەورە بێت.

55 is in slot 5 and is found at once. For 41 the function looks only at slot 1, finds 91 there, and knows that 41 is not stored: one comparison, whether the table has ten slots or ten million.

⁦55⁩ لە شوێنی 5دایە و یەکسەر دەدۆزرێتەوە. بۆ ⁦41⁩ تەنها سەیری شوێنی 1 دەکات، ⁦91⁩ لەوێ دەبینێت و دەزانێت ⁦41⁩ هەڵنەگیراوە: یەک بەراورد، دە شوێنی هەبێت یان دە ملیۆن.

Quick checkپشکنینی خێراWhy does hash_find(41) know after a single look that 41 is not stored?بۆچی hash_find(41) بە یەک سەیرکردن دەزانێت کە ⁦41⁩ هەڵنەگیراوە؟41 could only be in slot 41 % 10, which is 1, and slot 1 holds 91⁦41⁩ تەنها دەکرا لە شوێنی 41 % 10 (واتە ⁦1⁩) بێت و لە شوێنی 1دا ⁦91⁩ هەیەThe function first looks at all 10 slotsکردارەکە سەرەتا سەیری هەموو ⁦10⁩ شوێنەکە دەکات41 is bigger than every key in the table⁦41⁩ لە هەموو کلیلەکانی خشتەکە گەورەترە

Hashing: compute where the key isهاشکردن: شوێنی کلیلەکە بژمێرە

Collisions and the next free slotپێکدادانی هاش و شوێنی بەتاڵی دواتر

Add the key 47 to the table: 47 % 10 is 7, but slot 7 already holds 27. Two different keys that want the same slot cause a collision. One simple fix is linear probing: if the slot is taken, try the next one, then the next, and after the last slot go round to slot 0, until a free slot appears. Slot 8 holds 18, so 47 goes to slot 9.

⁦47⁩ بۆ خشتەکە زیاد بکە: 47 % 10 دەکاتە 7، بەڵام لە شوێنی 7دا پێشتر ⁦27⁩ هەیە. دوو جیاواز کە هەمان شوێنیان دەوێت دروست دەکەن. چارەسەرێکی سادە : ئەگەر شوێنەکە گیرابوو، شوێنی دواتر تاقی بکەرەوە و پاشان ئەوەی دوای ئەویش؛ دوای دوایین شوێن بگەڕێوە بۆ شوێنی 0، تا شوێنێکی بەتاڵ دەردەکەوێت. لە شوێنی 8دا ⁦18⁩ هەیە، بۆیە ⁦47⁩ دەچێتە شوێنی 9.

A collision at slot 7: linear probing tries slot 8, then slot 9. لە شوێنی 7: شوێنی 8 تاقی دەکاتەوە، پاشان شوێنی 9.CêIT

Hashing: compute where the key isهاشکردن: شوێنی کلیلەکە بژمێرە

Linear probing in Pythonپشکنینی هێڵی لە Pythonـدا

Searching must now follow the same path. Start at the key's own slot and keep moving to the next slot until you find the key or reach an empty slot: an empty slot proves the key was never stored, because an insert would have used it.

گەڕان ئێستا دەبێت هەمان ڕێگا بگرێتەبەر. لە شوێنی تایبەتی دەست پێ بکە و بەردەوام بچۆ بۆ شوێنی دواتر تا دەدۆزیتەوە یان دەگەیتە شوێنێکی بەتاڵ: شوێنی بەتاڵ دەیسەلمێنێت کە هەرگیز هەڵنەگیراوە، چونکە دانان ئەو شوێنەی بەکار دەهێنا.

A hash table with linear probingخشتەیەکی هاش بە پشکنینی هێڵیprobing.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

def insert(table, key):
    if None not in table:
        return -1                         # the table is full
    slot = key % len(table)
    while table[slot] is not None:        # taken: try the next slot
        slot = (slot + 1) % len(table)    # after the last slot, go back to 0
    table[slot] = key
    return slot


def find(table, key):
    slot = key % len(table)
    for looks in range(1, len(table) + 1):
        if table[slot] is None:
            return -1, looks              # an empty slot: the key is not in the table
        if table[slot] == key:
            return slot, looks
        slot = (slot + 1) % len(table)
    return -1, len(table)                 # every slot looked at


table = [None] * 10
for key in [27, 63, 4, 18, 91, 55, 30]:
    insert(table, key)
print("47 goes to slot", insert(table, 47))
print(table)
for key in [55, 47, 37]:
    print(key, "-> (slot, looks):", find(table, key))

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 2-3

A full table has no free slot: refuse instead of looping for ever.

کە پڕە هیچ شوێنێکی بەتاڵی نییە: ڕەتی بکەرەوە لەبری ئەوەی بۆ هەمیشە بخولێتەوە.

Lineدێڕی 6

% len(table) wraps round from the last slot to slot 0.

% len(table) لە دوایین شوێنەوە دەگەڕێتەوە بۆ شوێنی 0.

Lineدێڕی 14-15

An empty slot ends the search: the key is not in the table.

شوێنی بەتاڵ گەڕانەکە کۆتایی پێ دەهێنێت: لە خشتەکەدا نییە.

55 is still found with one look, 47 needs three (slots 7, 8, 9), and 37 needs six looks before slot 2 proves it is missing. Keys that collide pile up in a row of full slots, so lookups slow down as the table fills. A hash function that gives every key of a known set its own slot is a perfect hash function: no collisions, and every search needs exactly one look.

⁦55⁩ هێشتا بە یەک سەیرکردن دەدۆزرێتەوە، ⁦47⁩ سێی دەوێت (شوێنی 7، 8، ⁦9⁩) و ⁦37⁩ شەش سەیرکردنی دەوێت پێش ئەوەی شوێنی 2 بیسەلمێنێت کە نییە. ئەو پێکدادان دەکەن لە ڕیزێک شوێنی پڕدا کەڵەکە دەبن، بۆیە گەڕان کاتێک خشتەکە پڕ دەبێت هێواش دەبێت. کە بە هەر کۆمەڵێکی زانراو شوێنی تایبەتی خۆی بدات پێی دەوترێت : هیچ نییە و هەر گەڕانێک ڕێک یەک سەیرکردنی پێویستە.

Quick checkپشکنینی خێراSlots 3, 4 and 5 are full and slot 6 is empty. A key hashes to slot 3 and is not in slots 3, 4 or 5. What does the search conclude?شوێنەکانی 3، 4 و 5 پڕن و شوێنی 6 بەتاڵە. هاش دەکرێت بۆ شوێنی 3 و لە شوێنەکانی 3، 4 و 5دا نییە. گەڕانەکە چ ئەنجامێک وەردەگرێت؟The key is not in the tableکلیلەکە لە خشتەکەدا نییەIt must check every slot of the tableدەبێت هەموو شوێنەکانی خشتەکە بپشکنێتThe key is in slot 6کلیلەکە لە شوێنی 6دایە

Python already does this: dict and setPython پێشتر ئەمە دەکات: dict و set

You use hash tables every day without writing one. Python's dictionary and set are hash tables. Python computes a hash value for each key with hash(), uses it to choose a slot, handles collisions with its own clever probing order, and makes the table bigger before it gets too full. That is why key in prices and prices[key] take about the same time for ten keys or ten million, while in on a list must search one item after another.

هەموو ڕۆژێک بەکار دەهێنیت بەبێ ئەوەی یەکێکیان بنووسیت. و . بە hash() بۆ هەر دەژمێرێت، بۆ هەڵبژاردنی شوێنێک بەکاری دەهێنێت، بە ڕیزبەندیی پشکنینی زیرەکی خۆی چارەسەر دەکات و پێش ئەوەی خشتەکە زۆر پڕ ببێت گەورەی دەکات. هەر بۆیە key in prices و prices[key] بۆ دە یان دە ملیۆن نزیکەی هەمان کات دەبەن، لە کاتێکدا in لەسەر دەبێت یەک لە دوای یەک بگەڕێت.

To find a slot, a key needs a hash value that never changes. Such a value is hashable: numbers, strings and tuples of hashable values are, lists, sets and dictionaries are not. This is the reason behind the rule that dictionary keys and set items must be immutable (What can be a key?, A set as a quick check).

بۆ دۆزینەوەی شوێنێک، پێویستی بە هەیە کە هەرگیز ناگۆڕێت. وا : ژمارە، و ئەو تێدایە ، ، و نا. ئەمە هۆکاری ئەو یاسایەیە کە دەڵێت و دەبێت بن (چی دەتوانێت ببێتە کلیل؟، کۆمەڵەیەک وەک پشکنینێکی خێرا).

Definitionپێناسە

A Python value is hashable when it has a hash value that never changes, so it can be a key or a item. Numbers, strings and tuples of hashable values are hashable; lists, sets and dictionaries are not.

هاشهەڵگرە کاتێک هەیە کە هەرگیز ناگۆڕێت، بۆیە دەتوانێت ببێتە یان . ژمارە، و ئەو هاشهەڵگریان تێدایە هاشهەڵگرن؛ ، و نا.

hash() and hashable valueshash() و نرخی هاشهەڵگرpython_hashing.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

print(hash(27), hash(27) % 10)            # a small int is its own hash
print(hash(3.0) == hash(3))               # equal values, equal hashes
prices = {"tea": 500, "samoon": 250, "kebab": 3000}
print("kebab" in prices, prices["tea"])   # found by hash, not by a scan
print(hash((1, 2)) == hash((1, 2)))       # a tuple is hashable
print(hash([1, 2]))                       # a list is not

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 1

A small whole number is its own hash value, so % 10 gives the same slot as in our table.

بچووک خۆیەتی، بۆیە % 10 هەمان شوێن دەدات وەک لە خشتەکەی ئێمەدا.

Lineدێڕی 2

Values that are equal must have equal hashes, or a dictionary could not find them.

ئەو یەکسانن دەبێت یەکسانیان هەبێت، ئەگەرنا نەیدەتوانی بیاندۆزێتەوە.

Lineدێڕی 6

A list can change, so it has no fixed hash value.

دەتوانێت بگۆڕێت، بۆیە جێگیری نییە.

Quick checkپشکنینی خێراWhy can a list not be a dictionary key?بۆچی ناتوانێت ببێتە ؟Lists are too long to be comparedلیستەکان زۆر درێژن بۆ بەراوردکردنDictionaries accept only strings as keysفەرهەنگەکان تەنها زنجیرەنووسە وەک کلیل وەردەگرنA list can change, so it has no hash value that stays the sameلیستێک دەتوانێت بگۆڕێت، بۆیە نرخێکی هاشی نییە کە وەک خۆی بمێنێتەوە

Python already does this: dict and setPython پێشتر ئەمە دەکات: dict و set

How much faster is a set?کۆمەڵە چەندە خێراترە؟

How big is the difference? On the computer this lesson was written on, 100 searches for a missing number among a million took this long (timings differ between computers and between runs):

جیاوازییەکە چەندە گەورەیە؟ لەسەر ئەو ئەم وانەیەی لەسەر نووسراوە، ⁦100⁩ گەڕان بەدوای ژمارەیەکدا کە لە ناو ملیۆنێکدا نییە ئەمەندە کاتی برد (کاتەکان لە نێوان و لە نێوان کارپێکردنەکاندا جیاوازن):

in on a list and on a setin لەسەر لیستێک و لەسەر کۆمەڵەیەکlist_vs_set.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

import time

numbers = list(range(1_000_000))
number_set = set(numbers)
missing = -5                              # not there: the worst case for a list

start = time.perf_counter()
for _ in range(100):
    missing in numbers                    # linear search, 100 times
print(f"list: {time.perf_counter() - start:.3f} s")

start = time.perf_counter()
for _ in range(100):
    missing in number_set                 # hash lookup, 100 times
print(f"set:  {time.perf_counter() - start:.6f} s")

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 9

Linear search: a million comparisons each time.

: هەموو جارێک ملیۆنێک بەراورد.

Lineدێڕی 14

Hash lookup: one slot (or a few) each time.

گەڕانی هاش: هەموو جارێک یەک شوێن (یان چەند شوێنێک).

Common mistakesهەڵە باوەکان

Mistakeهەڵە	What happensچی ڕوو دەدات	Fixچارەسەر
Binary search on an unsorted list لەسەر ڕیزنەکراو	wrong answers and no error: 750 "not found" although it is at index 0وەڵامی هەڵە و هیچ : ⁦750⁩ «نەدۆزرایەوە» لە کاتێکدا لە 0دایە	sort first, or use linear searchسەرەتا ڕیز بکە، یان بەکار بهێنە
`last = len(values)` instead of `len(values) - 1last = len(values)` لەبری `len(values) - 1`	`IndexError: list index out of range` when the key is bigger than every item (for example 100)`IndexError: list index out of range` کاتێک لە هەموو گەورەترە (بۆ نموونە ⁦100⁩)	`last = len(values) - 1`
`while first < last:while first < last:`	when one item is left, it is never checked: 64 is reported as missing ( $-1$ )کاتێک تەنها یەک دەمێنێتەوە، ناپشکنرێت: ⁦64⁩ وەک نەبوو ڕادەگەیەنرێت ( $-1$ )	`while first <= last:`
`first = mid` or `last = midfirst = mid` یان `last = mid`	the part stops shrinking: an endless loop (searching 80 was still running after 50 rounds)بەشەکە بچووک نابێتەوە: (گەڕان بۆ ⁦80⁩ دوای ⁦50⁩ هەنگاو هێشتا بەردەوام بوو)	`first = mid + 1 / last = mid - 1`
`mid = (first + last) / 2mid = (first + last) / 2`	`TypeError: list indices must be integers or slices, not float`	`//`: floor division`//`:
With linear probing, checking only the key's own slotلەگەڵ ، پشکنینی تەنها شوێنی تایبەتی	keys moved by a collision are missed: 47 sits in slot 9, not 7ئەو بەهۆی جووڵێنراون ون دەبن: ⁦47⁩ لە شوێنی 9دایە، نەک 7	keep probing until the key or an empty slotبەردەوام بپشکنە تا یان شوێنێکی بەتاڵ
A list as a dictionary key وەک	`TypeError: unhashable type: 'list'`	use a tuple بەکار بهێنە

Exercisesڕاهێنانەکان

ExerciseڕاهێنانTrace a linear searchبەدواداچوون بۆ گەڕانی هێڵی

A shop's rice bags weigh [14, 3, 27, 8, 41, 3, 19, 30] kg. Search linearly for 27, 3, 30 and 50. For each key make a trace table (index, item, equal?) and give the result and the number of comparisons. What happens with 3, which appears twice?

کیسەکانی برنجی دوکانێک [14, 3, 27, 8, 41, 3, 19, 30] کیلۆن. بە بەدوای ⁦27⁩، 3، ⁦30⁩ و ⁦50⁩دا بگەڕێ. بۆ هەر دروست بکە (، ، یەکسانە؟) و ئەنجام و ژمارەی بەراوردەکان بنووسە. لەگەڵ 3 کە دوو جار هاتووە چی ڕوو دەدات؟

Show answerوەڵامەکە پیشان بدە

Key	Comparisonsبەراورد	Resultئەنجام
27	3	index 2 2
3	2	index 1: the first 3; the 3 at index 5 is never reached 1: یەکەم 3؛ ئەو 3ەی لە 5دایە هەرگیز پێی ناگات
30	8	index 7: the last item, the worst case for a present key 7: دوایین ، بۆ کە هەیە
50	8	$-1$ : missing, every item compared $-1$ : نییە، هەموو بەراورد کرا

The trace, printed by the programبەدواداچوونەکە، کە بەرنامەکە چاپی دەکاتex_linear_trace.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

def linear_search_trace(values, key):
    for index in range(len(values)):
        same = values[index] == key
        print(f"  index {index}: {values[index]:>2} == {key}? {same}")
        if same:
            return index
    return -1


bags = [14, 3, 27, 8, 41, 3, 19, 30]       # rice bags in a shop, kg
for key in [27, 3, 30, 50]:
    print(f"key {key}:")
    print("  result:", linear_search_trace(bags, key))

ExerciseڕاهێنانBinary search on ten numbersگەڕانی دووانی لەسەر دە ژمارە

Heights in metres above or below a river's normal level are kept sorted: [-12, -5, 0, 4, 9, 16, 23, 31, 38, 45]. Trace binary search for 31, $-12$ and 10: give first, last and mid in each round, and the result.

بەرزییەکان بە مەتر لە سەرەوە یان خوارەوەی ئاستی ئاسایی ڕووبارێک بە ڕیزکراوی هەڵگیراون: [-12, -5, 0, 4, 9, 16, 23, 31, 38, 45]. بەدواداچوون بۆ بکە بۆ ⁦31⁩، $-12$ و ⁦10: first⁩، last و mid لە هەر هەنگاوێکدا و ئەنجامەکە بنووسە.

Show answerوەڵامەکە پیشان بدە

Rounds printed by the programهەنگاوەکان کە بەرنامەکە چاپیان دەکاتex_binary10.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

def binary_search_rounds(values, key):
    first, last = 0, len(values) - 1
    rounds = 0
    while first <= last:
        mid = (first + last) // 2
        rounds += 1
        print(f"  round {rounds}: first={first} last={last} mid={mid} -> {values[mid]}")
        if values[mid] == key:
            return mid
        elif key < values[mid]:
            last = mid - 1
        else:
            first = mid + 1
    return -1


heights = [-12, -5, 0, 4, 9, 16, 23, 31, 38, 45]     # metres above or below a river's normal level
for key in [31, -12, 10]:
    print(f"key {key}:")
    print("  index:", binary_search_rounds(heights, key))

31 is found in 2 rounds and $-12$ in 3. 10 is missing: after mid = 5 (16 > 10) last becomes 4 while first is 5, so the search ends after 3 rounds and returns $-1$ . No search in 10 items needs more than $\lfloor \log_2 10 \rfloor + 1 = 4$ rounds.

⁦31⁩ لە 2 هەنگاودا و $-12$ لە 3 هەنگاودا دەدۆزرێتەوە. ⁦10⁩ نییە: دوای mid = 5 (16 > 10) last دەبێتە 4 لە کاتێکدا first 5ـە، بۆیە گەڕانەکە دوای 3 هەنگاو کۆتایی دێت و $-1$ دەگەڕێنێتەوە. هیچ گەڕانێک لە ⁦10⁩ لە $\lfloor \log_2 10 \rfloor + 1 = 4$ هەنگاو زیاتری ناوێت.

ExerciseڕاهێنانDoes sorting pay off?ئایا ڕیزکردن قازانجی هەیە؟

Take the 24 unsorted numbers [62, 7, 85, 23, 4, 91, 38, 15, 70, 2, 56, 44, 97, 11, 29, 80, 66, 9, 50, 33, 74, 18, 88, 41]. (a) Count the comparisons of a linear search for 2, 41, 66 and 100. (b) Sort the list and count again. (c) Count the rounds of a binary search on the sorted list. (d) Do the same with the 16 words printer, mouse, keyboard, monitor, laptop, router, server, cable, screen, camera, speaker, tablet, phone, battery, charger, modem and the keys cable, router, tablet and scanner. What do you notice?

ئەم ⁦24⁩ ژمارە ڕیزنەکراوە وەربگرە [62, 7, 85, 23, 4, 91, 38, 15, 70, 2, 56, 44, 97, 11, 29, 80, 66, 9, 50, 33, 74, 18, 88, 41]. (أ) بەراوردەکانی بۆ 2، ⁦41⁩، ⁦66⁩ و ⁦100⁩ بژمێرە. (ب) ڕیز بکە و دووبارە بیژمێرە. (ج) هەنگاوەکانی لەسەر ڕیزکراو بژمێرە. (د) هەمان کار بکە بە ⁦16⁩ وشەکەی printer, mouse, keyboard, monitor, laptop, router, server, cable, screen, camera, speaker, tablet, phone, battery, charger, modem و cable، router، tablet و scanner. تێبینی چی دەکەیت؟

Show answerوەڵامەکە پیشان بدە

Counting comparisons before and after sortingژماردنی بەراورد پێش و دوای ڕیزکردنex_compare24.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

def linear_count(values, key):
    comparisons = 0
    for v in values:
        comparisons += 1
        if v == key:
            break
    return comparisons


def binary_count(values, key):
    first, last = 0, len(values) - 1
    rounds = 0
    while first <= last:
        mid = (first + last) // 2
        rounds += 1
        if values[mid] == key:
            break
        elif key < values[mid]:
            last = mid - 1
        else:
            first = mid + 1
    return rounds


numbers = [62, 7, 85, 23, 4, 91, 38, 15, 70, 2, 56, 44,
           97, 11, 29, 80, 66, 9, 50, 33, 74, 18, 88, 41]
keys = [2, 41, 66, 100]
print("unsorted, linear:", [linear_count(numbers, k) for k in keys])
numbers.sort()
print("sorted, linear:  ", [linear_count(numbers, k) for k in keys])
print("sorted, binary:  ", [binary_count(numbers, k) for k in keys])

words = ["printer", "mouse", "keyboard", "monitor", "laptop", "router", "server", "cable",
         "screen", "camera", "speaker", "tablet", "phone", "battery", "charger", "modem"]
wkeys = ["cable", "router", "tablet", "scanner"]
print("words unsorted, linear:", [linear_count(words, k) for k in wkeys])
words.sort()
print(words)
print("words sorted, linear:  ", [linear_count(words, k) for k in wkeys])
print("words sorted, binary:  ", [binary_count(words, k) for k in wkeys])

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 1-7

Linear search that counts and stops at the first match.

کە دەژمێرێت و لە یەکەم یەکسانیدا دەوەستێت.

Lineدێڕی 10-22

Binary search that counts its rounds.

کە هەنگاوەکانی دەژمێرێت.

Sorting alone does not always help linear search: 2 moved to the front (from 10 comparisons to 1), but router moved back (from 6 to 12), and a missing key still costs every item (24 and 16). Binary search on the sorted data never needs more than 5 rounds for 24 numbers or 16 words, because $\lfloor \log_2 24 \rfloor + 1 = 5$ and $\lfloor \log_2 16 \rfloor + 1 = 5$ . Sorting pays off when you then use binary search, and search many times.

بە تەنها هەمیشە یارمەتیی نادات: 2 چووە پێشەوە (لە ⁦10⁩ بەراوردەوە بۆ ⁦1⁩)، بەڵام router چووە دواوە (لە 6ـەوە بۆ ⁦12⁩) و کە نییە هێشتا هەموو دەخایەنێت (⁦24⁩ و ⁦16⁩). لەسەر ڕیزکراو بۆ ⁦24⁩ ژمارە یان ⁦16⁩ وشە هەرگیز لە 5 هەنگاو زیاتری ناوێت، چونکە $\lfloor \log_2 24 \rfloor + 1 = 5$ و $\lfloor \log_2 16 \rfloor + 1 = 5$ . قازانج دەکات کاتێک پاشان بەکار دەهێنیت و زۆر جار دەگەڕێیت.

ExerciseڕاهێنانHashing with % 11هاشکردن بە % 11

Store the keys [44, 121, 55, 33, 110, 77, 22, 66] in a hash table of 11 slots with h(k) = k % 11. (a) Which slot does each key get? (b) What happens if the table has no collision handling? (c) Use linear probing and search for 11, 44, 88 and 121: how many looks does each search take? (d) Try 10 slots with k % 10 instead.

[44, 121, 55, 33, 110, 77, 22, 66] لە بە ⁦11⁩ شوێن بە h(k) = k % 11 هەڵبگرە. (أ) هەر کام شوێن وەردەگرێت؟ (ب) ئەگەر خشتەکە هیچ چارەسەرێکی بۆ نەبێت چی ڕوو دەدات؟ (ج) بەکار بهێنە و بەدوای ⁦11⁩، ⁦44⁩، ⁦88⁩ و ⁦121⁩دا بگەڕێ: هەر گەڕانێک چەند سەیرکردن دەخایەنێت؟ (د) لەبری ئەوە ⁦10⁩ شوێن بە k % 10 تاقی بکەرەوە.

Show answerوەڵامەکە پیشان بدە

Every key is a multiple of 11هەموو کلیلێک چەندجارەیەکی ⁦11⁩ـەex_hash11.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

from probing_funcs import insert, find

keys = [44, 121, 55, 33, 110, 77, 22, 66]
print([k % 11 for k in keys])             # the slot of each key

naive = [None] * 11                       # no collision handling
for k in keys:
    naive[k % 11] = k                     # later keys overwrite earlier ones
print(naive)

table = [None] * 11                       # with linear probing
for k in keys:
    insert(table, k)
print(table)
for k in [11, 44, 88, 121]:
    print(k, find(table, k))

ten = [None] * 10                         # the same keys, 10 slots
for k in keys:
    insert(ten, k)
print(ten)

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 1

insert() and find() are the two functions of the linear-probing program above, saved in the file probing_funcs.py.

insert() و find() هەمان دوو لە سەرەوە، لە probing_funcs.pyدا هەڵگیراون.

(a) Every key is a multiple of 11, so every key hashes to slot 0. (b) Without collision handling each key overwrites the one before: only 66 is left. (c) With linear probing the keys fill slots 0 to 7 in order; 44 takes 1 look, 121 takes 2, and the missing keys 11 and 88 take 9 looks each, until the empty slot 8. The "one look" promise of hashing is lost. (d) With 10 slots, k % 10 sends the eight keys to eight different slots: for these keys it is a perfect hash function. A hash function must spread the keys; one that fits the data badly makes a hash table no faster than a list.

(أ) هەموو چەندجارەیەکی ⁦11⁩ـە، بۆیە هەموو بۆ شوێنی 0 هاش دەکرێن. (ب) بەبێ چارەسەری ، هەر ئەوەی پێشوو دەسڕێتەوە: تەنها ⁦66⁩ دەمێنێتەوە. (ج) بە بە ڕیز شوێنەکانی 0 تا 7 پڕ دەکەنەوە؛ ⁦44⁩ یەک سەیرکردن، ⁦121⁩ دوو و ⁦11⁩ و ⁦88⁩ کە نین هەر یەکەیان 9 سەیرکردن دەخایەنن، تا شوێنی بەتاڵی 8. بەڵێنی «یەک سەیرکردن»ـی هاشکردن ون دەبێت. (د) بە ⁦10⁩ شوێن، k % 10 هەشت دەنێرێتە هەشت شوێنی جیاواز: k % 10 بۆ ئەم وەک کار دەکات. دەبێت بڵاو بکاتەوە؛ کە لەگەڵ خراپ بگونجێت لە خێراتر ناکات.

ExerciseڕاهێنانCountries and capitalsوڵات و پایتەخت

Build a small table of countries and their capitals with two lists of 12 slots, one for the keys and one for the values at the same index. Use the length of the country's name as its hash value and linear probing for collisions. Store Iraq, Syria, Turkey, Lebanon, Azerbaijan and Iran, then look up Iran, Turkey and Egypt. Which names collide?

خشتەیەکی بچووک بۆ وڵاتەکان و پایتەختەکانیان دروست بکە بە دوو بە ⁦12⁩ شوێن، یەکێکیان بۆ و ئەوی تر بۆ لە هەمان . درێژیی ناوی وڵات وەک و بۆ بەکار بهێنە. Iraq، Syria، Turkey، Lebanon، Azerbaijan و Iran هەڵبگرە، پاشان بەدوای Iran، Turkey و Egyptـدا بگەڕێ. کام ناوانە پێکدادان دەکەن؟

Show answerوەڵامەکە پیشان بدە

Two parallel lists as a hash tableدوو لیستی تەریب وەک خشتەیەکی هاشex_countries.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

SIZE = 12
countries = [None] * SIZE                 # keys
capitals = [None] * SIZE                  # values, at the same index


def put(country, capital):
    slot = len(country) % SIZE            # hash = length of the name
    while countries[slot] is not None:    # collision: next free slot
        slot = (slot + 1) % SIZE
    countries[slot] = country
    capitals[slot] = capital


def get(country):
    slot = len(country) % SIZE
    while countries[slot] is not None:
        if countries[slot] == country:
            return capitals[slot]
        slot = (slot + 1) % SIZE
    return None


for country, capital in [("Iraq", "Baghdad"), ("Syria", "Damascus"), ("Turkey", "Ankara"),
                         ("Lebanon", "Beirut"), ("Azerbaijan", "Baku"), ("Iran", "Tehran")]:
    put(country, capital)
print(countries)
for name in ["Iran", "Turkey", "Egypt"]:
    print(name, "->", get(name))

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 7

hash value = number of letters in the name

= ژمارەی پیتەکانی ناوەکە

Lineدێڕی 10-11

The capital is stored at the same index as its country.

پایتەخت لە هەمان وڵاتەکەیدا هەڵدەگیرێت.

Iraq and Iran both have 4 letters, so Iran collides with Iraq and moves past Syria (5), Turkey (6) and Lebanon (7) to slot 8. Looking up Iran therefore takes 5 looks, Turkey 1, and Egypt (5 letters) looks at slots 5, 6, 7 and 8 before the empty slot 9 shows it is missing. Name length is a poor hash: many names have the same length, and most country names have between 4 and 12 letters, so in a big table most slots stay empty while a few are crowded.

Iraq و Iran هەردووکیان 4 پیتیان هەیە، بۆیە Iran لەگەڵ Iraq پێکدادان دەکات و بە ⁦Syria (5)⁩، ⁦Turkey (6)⁩ و ⁦Lebanon (7)⁩دا تێدەپەڕێت تا شوێنی 8. بۆیە گەڕان بەدوای Iranـدا 5 سەیرکردن دەخایەنێت، ⁦Turkey 1⁩ و ⁦Egypt (5⁩ پیت) سەیری شوێنەکانی 5، 6، 7 و 8 دەکات پێش ئەوەی شوێنی بەتاڵی 9 پیشانی بدات کە نییە. درێژیی ناو خراپە: زۆر ناو هەمان درێژییان هەیە و زۆربەی ناوی وڵاتان لە نێوان 4 تا ⁦12⁩ پیتدان، بۆیە لە گەورەدا زۆربەی شوێنەکان بەتاڵ دەمێننەوە لە کاتێکدا چەند شوێنێک قەرەباڵغن.

Summary of the lessonپوختەی وانەکە

Linear search checks items one by one: 1 comparison at best, $n$ at worst, and it works on any list.
Binary search needs a sorted list: compare with the middle, keep one half, repeat until the key is found or first > last. At most $\lfloor \log_2 n \rfloor + 1$ looks: logarithmic time. On unsorted data it gives wrong answers without an error.
Python's bisect module does binary search for you; databases use sorted indexes for the same reason.
Hashing computes the slot of a key, for example k % size, so one look is usually enough. Two keys in one slot are a collision; linear probing moves on to the next free slot, and a perfect hash function has no collisions.
Python's dict and set are hash tables; that is why their keys must be hashable.

یەک یەک دەپشکنێت: لە 1 بەراورد، لە $n$ و لەسەر هەر کار دەکات.
ڕیزکراوی پێویستە: لەگەڵ ناوەڕاست بەراورد بکە، نیوەیەک بهێڵەوە، دووبارە بکەرەوە تا دەدۆزرێتەوە یان first > last. لانیزۆر $\lfloor \log_2 n \rfloor + 1$ سەیرکردن: . لەسەر ڕیزنەکراو وەڵامی هەڵە دەدات، بەبێ هیچ .
bisectـی بۆ دەکات؛ لەبەر هەمان هۆکار ڕیزکراو بەکار دەهێنن.
هاشکردن شوێنی دەژمێرێت، بۆ نموونە k % size، بۆیە زۆرجار یەک سەیرکردن بەسە. دوو لە یەک شوێندا ؛ دەچێتە سەر شوێنی بەتاڵی دواتر و هیچ نییە.
و ؛ هەر بۆیە دەبێت بن.

Review questionsپرسیارەکانی پێداچوونەوە

When is binary search allowed?گەڕانی دووانی کەی ڕێگەپێدراوە؟

Only on a sorted list (ascending, or descending with the comparison flipped).

تەنها لەسەر ڕیزکراو (بەرزبوونەوە، یان نزمبوونەوە بە پێچەوانەکردنەوەی بەراوردەکە).

At most how many looks does binary search need for 1,000,000 sorted items?گەڕانی دووانی بۆ ⁦1,000,000⁩ دانەی ڕیزکراو لانیزۆر چەند سەیرکردنی دەوێت؟

20, because $\lfloor \log_2 1\,000\,000 \rfloor + 1 = 20$ .

⁦20⁩، چونکە $\lfloor \log_2 1\,000\,000 \rfloor + 1 = 20$ .

What is a collision, and how does linear probing handle it?پێکدادانی هاش چییە و پشکنینی هێڵی چۆن چارەسەری دەکات؟

Two keys hash to the same slot; linear probing stores the second key in the next free slot and searches the same way, stopping at an empty slot.

دوو بۆ هەمان شوێن هاش دەکرێن؛ دووەم لە شوێنی بەتاڵی دواتردا هەڵدەگرێت و بە هەمان شێوە دەگەڕێت و لە شوێنێکی بەتاڵدا دەوەستێت.

Why is x in my_set fast but x in my_list slow for big collections?بۆچی x in my_set خێرایە بەڵام x in my_list بۆ دراوەی زۆر هێواشە؟

A set is a hash table: it computes the slot of x. A list must be searched linearly.

: شوێنی x دەژمێرێت. دەبێت بە هێڵی بگەڕێت.

The chapter in one lookبەشەکە بە یەک سەیرکردن

The chapter "Data Structures and Algorithms" ends with this lesson. Its five ideas side by side:

بەشی « و » بەم وانەیە کۆتایی دێت. پێنج بیرۆکەکەی لە تەنیشت یەکەوە:

Topicبابەت	The ideaبیرۆکەکە	In Pythonلە	Lessonوانە
stack	last in, first outدوایین هاتوو، یەکەم دەرچوو	`append() / pop()`	Stacksوانەی ستاکەکان
queue	first in, first outیەکەم هاتوو، یەکەم دەرچوو	`deque: append() / popleft()`	Queues and dequesکیووەکان و کیووە دووسەرەکان
deque	add and remove at both endsزیادکردن و لابردن لە هەردوو سەرەوە	`appendleft() / pop()`	The dequeهەمان وانە: کیووی دووسەرە
sorting	bubble and insertion sort are quadratic; Python's sort is about $n \log n$ و پلەدوون؛ نزیکەی $n \log n$ ـە	`sort() / sorted()`	Sorting algorithmsئەلگۆریزمەکانی ڕیزکردن
searchingگەڕان	linear, binary (logarithmic) and hashingهێڵی، دووانی (لۆگاریتمی) و هاشکردن	`in / bisect / dict / set`	this lessonئەم وانەیە

Where you meet these again: an AI agent searching a maze keeps its frontier in a stack for depth-first search and in a queue for breadth-first search (DFS, BFS), and in a priority queue built on a heap for its cleverer searches (priority queues); that kind of search is introduced in Search problems. Databases keep sorted indexes so that a query can find its rows without reading the whole table (indexes).

لە کوێ دیسان ئەمانە دەبینیتەوە: کە لە دەگەڕێت، بۆ لە و بۆ لە هەڵدەگرێت (DFS، BFS)، هەروەها بۆ گەڕانە زیرەکترەکانی لە کە لەسەر دروست کراوە (کیووە پێشینەییەکان)؛ ئەو جۆرە گەڕانە لە کێشەکانی گەڕان دەناسێنرێت. ڕیزکراو هەڵدەگرن بۆ ئەوەی بەبێ خوێندنەوەی هەموو خۆی بدۆزێتەوە (پێڕستەکان).

Videoڤیدیۆ

Watch a videoسەیری ڤیدیۆیەک بکە

A video that viewers liked a lot and praised in their comments, chosen for this lesson.ڤیدیۆیەک کە بینەران زۆریان پێ خۆش بووە و لە کۆمێنتەکانیاندا ستایشیان کردووە، بۆ ئەم وانەیە هەڵبژێردراوە.

How Binary Search Makes Computers Much, Much FasterTom Scott · Englishئینگلیزی · 1.6M viewsبینین · 79K likesلایک · Partبەشی 1:43–6:51 (ofلە 6:51)
Why searching sorted data is so much faster: linear search against binary search, with dictionaries, libraries and database indexes.
بۆچی گەڕان لە ڕیزکراودا زۆر خێراترە: بەرامبەر ، بە نموونەی فەرهەنگی کاغەزی، کتێبخانە و .
Watch from 1:43: sorted data and an index, linear search against binary search, and database indexes.
لە ⁦1:43⁩ بەدواوە سەیر بکە: ڕیزکراو و ، بەرامبەر و .

Lesson complete!وانەکە تەواو بوو!

Well done. Review the key terms, then go on to the next lesson.دەستخۆش. سەیرێکی زاراوە سەرەکییەکان بکەرەوە، پاشان بڕۆ بۆ وانەی داهاتوو.

Key termsزاراوە سەرەکییەکان

Next lessonوانەی داهاتوو

Project: Binary to Decimal Converterپڕۆژیلە: گۆڕینی دووانی بۆ دەیی

Related lecturesوانە پەیوەندیدارەکان

References and further readingسەرچاوەکان و خوێندنەوەی زیاتر

This lecture is a first edition. The Kurdish text and terminology are waiting for review by Kurdish IT teachers.ئەم وانەیە چاپی یەکەمە. دەقە کوردییەکە و زاراوەکانی چاوەڕێی پێداچوونەوەی مامۆستایانی کوردی بواری IT ن.

Binary Search and Hashingگەڕانی دووانی و هاشکردن

What you will learnچی فێر دەبیت

What is searching?گەڕان چییە؟

Linear search in one screenگەڕانی هێڵی لە یەک پەڕەدا

Binary search: always look in the middleگەڕانی دووانی: هەمیشە سەیری ناوەڕاست بکە

The algorithm step by stepئەلگۆریزمەکە هەنگاو بە هەنگاو

Trace 1: the key is in the listبەدواداچوونی یەکەم: کلیلەکە لە لیستەکەدا هەیە

Trace 2: the key is missingبەدواداچوونی دووەم: کلیلەکە نییە

Binary search in Pythonگەڕانی دووانی لە Pythonـدا

Reading the list, and counting roundsخوێندنەوەی لیست و ژماردنی هەنگاوەکان

Unsorted lists and largest-first listsلیستێکی ڕیزنەکراو و گەورەترین لە سەرەتادا

How many steps? Logarithmic timeچەند هەنگاو؟ کاتی لۆگاریتمی

The 2302^{30}230 questionپرسیاری 2302^{30}230

Where binary search is usedگەڕانی دووانی لە کوێ بەکار دێت؟

Python's bisect moduleمۆدیوڵی bisectـی Python

Hashing: compute where the key isهاشکردن: شوێنی کلیلەکە بژمێرە

A hash table in Pythonخشتەیەکی هاش لە Pythonـدا

Collisions and the next free slotپێکدادانی هاش و شوێنی بەتاڵی دواتر

Linear probing in Pythonپشکنینی هێڵی لە Pythonـدا

Python already does this: dict and setPython پێشتر ئەمە دەکات: dict و set

How much faster is a set?کۆمەڵە چەندە خێراترە؟

Common mistakesهەڵە باوەکان

Exercisesڕاهێنانەکان

Summary of the lessonپوختەی وانەکە

The chapter in one lookبەشەکە بە یەک سەیرکردن

Watch a videoسەیری ڤیدیۆیەک بکە

Lesson complete!وانەکە تەواو بوو!

Key termsزاراوە سەرەکییەکان

Related lecturesوانە پەیوەندیدارەکان

The $2^{30}$ questionپرسیاری $2^{30}$

Python's bisect moduleمۆدیوڵی `bisect`ـی Python