Trò chơi đoán tìm kiếm nhị phân python

Nếu bạn thấy thông báo này, điều đó có nghĩa là chúng tôi đang gặp sự cố khi tải các tài nguyên bên ngoài trên trang web của mình

Nếu bạn đang sử dụng bộ lọc web, vui lòng đảm bảo rằng các miền *. kastatic. tổ chức và *. kasandbox. org được bỏ chặn

Giả sử bây giờ máy tính sẽ cho bạn biết sau mỗi lần đoán sai.

>>> from random import randint
>>> L = [randint(10, 99) for _ in range(10)]
>>> L
[32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
>>> 10 in L
False
>>> 81 in L
True
>>> L.index(81)
3
>>> L[3]
81

4 hoặc

>>> from random import randint
>>> L = [randint(10, 99) for _ in range(10)]
>>> L
[32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
>>> 10 in L
False
>>> 81 in L
True
>>> L.index(81)
3
>>> L[3]
81

5. Với cùng chi phí và giá cả, bây giờ bạn có chơi trò chơi này không?

Một ví dụ về phiên trò chơi với phản hồi

>>> from random import randint
>>> L = [randint(10, 99) for _ in range(10)]
>>> L
[32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
>>> 10 in L
False
>>> 81 in L
True
>>> L.index(81)
3
>>> L[3]
81

4 và

>>> from random import randint
>>> L = [randint(10, 99) for _ in range(10)]
>>> L
[32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
>>> 10 in L
False
>>> 81 in L
True
>>> L.index(81)
3
>>> L[3]
81

5 được hiển thị bên dưới

$ python findsecret.py
Guess number in [0, 1000] : 500
Your guess is too low.
Guess number in [0, 1000] : 750
Your guess is too high.
Guess number in [0, 1000] : 625
Your guess is too high.
Guess number in [0, 1000] : 562
Your guess is too high.
Guess number in [0, 1000] : 531
Your guess is too high.
Guess number in [0, 1000] : 516
Your guess is too high.
Guess number in [0, 1000] : 508
Your guess is too high.
Guess number in [0, 1000] : 504
Your guess is too low.
Guess number in [0, 1000] : 506
found 506 after 9 guesses

Không gian tìm kiếm là [0, 1000] khi bắt đầu, trong Hình. 38 .

Hình. 38 Giảm một nửa không gian tìm kiếm trong mỗi bước.

Như minh họa trong Hình. 38 , trong mỗi bước, không gian tìm kiếm bị cắt làm đôi. Sau 10 bước, chúng tôi xuống chữ số cuối cùng. Trong mỗi bước chúng tôi khôi phục một chút bí mật.

Tìm kiếm nhị phân¶

Hãy để chúng tôi tạo một danh sách gồm 10 số có hai chữ số ngẫu nhiên. Hãy xem xét phiên dưới đây

>>> from random import randint
>>> L = [randint(10, 99) for _ in range(10)]
>>> L
[32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
>>> 10 in L
False
>>> 81 in L
True
>>> L.index(81)
3
>>> L[3]
81

Lệnh

>>> from random import randint
>>> L = [randint(10, 99) for _ in range(10)]
>>> L
[32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
>>> 10 in L
False
>>> 81 in L
True
>>> L.index(81)
3
>>> L[3]
81

8 sẽ ném ra một

>>> from random import randint
>>> L = [randint(10, 99) for _ in range(10)]
>>> L
[32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
>>> 10 in L
False
>>> 81 in L
True
>>> L.index(81)
3
>>> L[3]
81

9 nếu

def linear_search(numbers, nbr):
    """
    Returns -1 if nbr belongs to numbers,
    else returns k for which numbers[k] == nbr.
    Items in the list numbers must be sorted
    in increasing order.
    """
    for i in range(len(numbers)):
        if numbers[i] == nbr:
            return i
        elif numbers[i] > nbr:
            return -1
    return -1

0

Công thức đầu vào/đầu ra của vấn đề tìm kiếm dưới đây

\[\begin{split}\begin{array}{rcl} Đầu vào &. & \mbox{\tt L} \mbox{ danh sách các số và một số } \mbox {\tt x}. \\ Đầu ra &. & \mbox{index } \mbox{\tt k == -1}, \mbox{if } \mbox{\tt not x in L} \mbox{ other } \mbox{\tt L[k] == x . \end{mảng}\end{split}\]

Thuật toán tìm kiếm tuyến tính thực hiện các bước sau

1. Liệt kê trong

   def linear_search(numbers, nbr):
       """
       Returns -1 if nbr belongs to numbers,
       else returns k for which numbers[k] == nbr.
       Items in the list numbers must be sorted
       in increasing order.
       """
       for i in range(len(numbers)):
           if numbers[i] == nbr:
               return i
           elif numbers[i] > nbr:
               return -1
       return -1
   

   1 tất cả các phần tử của nó trong

   def linear_search(numbers, nbr):
       """
       Returns -1 if nbr belongs to numbers,
       else returns k for which numbers[k] == nbr.
       Items in the list numbers must be sorted
       in increasing order.
       """
       for i in range(len(numbers)):
           if numbers[i] == nbr:
               return i
           elif numbers[i] > nbr:
               return -1
       return -1
   

   2
2. Nếu

   def linear_search(numbers, nbr):
       """
       Returns -1 if nbr belongs to numbers,
       else returns k for which numbers[k] == nbr.
       Items in the list numbers must be sorted
       in increasing order.
       """
       for i in range(len(numbers)):
           if numbers[i] == nbr:
               return i
           elif numbers[i] > nbr:
               return -1
       return -1
   

   3 thì

   def linear_search(numbers, nbr):
       """
       Returns -1 if nbr belongs to numbers,
       else returns k for which numbers[k] == nbr.
       Items in the list numbers must be sorted
       in increasing order.
       """
       for i in range(len(numbers)):
           if numbers[i] == nbr:
               return i
           elif numbers[i] > nbr:
               return -1
       return -1
   

   4
3. Trả về

   def linear_search(numbers, nbr):
       """
       Returns -1 if nbr belongs to numbers,
       else returns k for which numbers[k] == nbr.
       Items in the list numbers must be sorted
       in increasing order.
       """
       for i in range(len(numbers)):
           if numbers[i] == nbr:
               return i
           elif numbers[i] > nbr:
               return -1
       return -1
   

   5 ở cuối vòng lặp

Phân tích chi phí của chúng tôi trước tiên xem xét trường hợp tốt nhất. Trong trường hợp tốt nhất, chúng tôi tìm thấy

def linear_search(numbers, nbr):
    """
    Returns -1 if nbr belongs to numbers,
    else returns k for which numbers[k] == nbr.
    Items in the list numbers must be sorted
    in increasing order.
    """
    for i in range(len(numbers)):
        if numbers[i] == nbr:
            return i
        elif numbers[i] > nbr:
            return -1
    return -1

6 ngay lập tức nếu

def linear_search(numbers, nbr):
    """
    Returns -1 if nbr belongs to numbers,
    else returns k for which numbers[k] == nbr.
    Items in the list numbers must be sorted
    in increasing order.
    """
    for i in range(len(numbers)):
        if numbers[i] == nbr:
            return i
        elif numbers[i] > nbr:
            return -1
    return -1

6 xảy ra ở đầu

def linear_search(numbers, nbr):
    """
    Returns -1 if nbr belongs to numbers,
    else returns k for which numbers[k] == nbr.
    Items in the list numbers must be sorted
    in increasing order.
    """
    for i in range(len(numbers)):
        if numbers[i] == nbr:
            return i
        elif numbers[i] > nbr:
            return -1
    return -1

1. Trong trường hợp xấu nhất, chúng ta phải duyệt toàn bộ danh sách nếu

def linear_search(numbers, nbr):
    """
    Returns -1 if nbr belongs to numbers,
    else returns k for which numbers[k] == nbr.
    Items in the list numbers must be sorted
    in increasing order.
    """
    for i in range(len(numbers)):
        if numbers[i] == nbr:
            return i
        elif numbers[i] > nbr:
            return -1
    return -1

6 ở cuối

def linear_search(numbers, nbr):
    """
    Returns -1 if nbr belongs to numbers,
    else returns k for which numbers[k] == nbr.
    Items in the list numbers must be sorted
    in increasing order.
    """
    for i in range(len(numbers)):
        if numbers[i] == nbr:
            return i
        elif numbers[i] > nbr:
            return -1
    return -1

1. Trung bình, chúng tôi thực hiện các bước \(c \times n\) , trong đó \(n =~\) . 5\)

>>> from random import randint
>>> L = [randint(10, 99) for _ in range(10)]
>>> L
[32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
>>> 10 in L
False
>>> 81 in L
True
>>> L.index(81)
3
>>> L[3]
81

91, for some constant \(c \approx 0.5\) . Ta nói chi phí của nó là \(O(n)\) .

Mã để tìm kiếm tuyến tính trong một danh sách được sắp xếp bên dưới. Để sắp xếp một danh sách

def linear_search(numbers, nbr):
    """
    Returns -1 if nbr belongs to numbers,
    else returns k for which numbers[k] == nbr.
    Items in the list numbers must be sorted
    in increasing order.
    """
    for i in range(len(numbers)):
        if numbers[i] == nbr:
            return i
        elif numbers[i] > nbr:
            return -1
    return -1

1, hãy thực hiện

>>> from random import randint
>>> L = [randint(10, 99) for _ in range(10)]
>>> L
[32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
>>> 10 in L
False
>>> 81 in L
True
>>> L.index(81)
3
>>> L[3]
81

93

________số 8

Nội dung dựng sẵn

>>> from random import randint
>>> L = [randint(10, 99) for _ in range(10)]
>>> L
[32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
>>> 10 in L
False
>>> 81 in L
True
>>> L.index(81)
3
>>> L[3]
81

94 và

>>> from random import randint
>>> L = [randint(10, 99) for _ in range(10)]
>>> L
[32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
>>> 10 in L
False
>>> 81 in L
True
>>> L.index(81)
3
>>> L[3]
81

95 cho danh sách không khai thác thứ tự

Báo cáo vấn đề để tìm kiếm trong một danh sách được sắp xếp bên dưới

\[\begin{split}\begin{array}{rcl} Đầu vào &. & \mbox{\tt L} \mbox{ là danh sách các số, được sắp xếp tăng dần;} \mbox{\tt x} \mbox{ là một số. } \\ Đầu ra &. & \mbox{\tt True} \mbox{ if } \mbox{\tt x in L}, \mbox{\tt False} \mbox{ ngược lại. } \end{mảng}\end{split}\]

Các quy tắc để áp dụng chia để trị là

• Các trường hợp cơ bản là

  >>> from random import randint
  >>> L = [randint(10, 99) for _ in range(10)]
  >>> L
  [32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
  >>> 10 in L
  False
  >>> 81 in L
  True
  >>> L.index(81)
  3
  >>> L[3]
  81
  

  96 và

  >>> from random import randint
  >>> L = [randint(10, 99) for _ in range(10)]
  >>> L
  [32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
  >>> 10 in L
  False
  >>> 81 in L
  True
  >>> L.index(81)
  3
  >>> L[3]
  81
  

  97
• Hãy để

  >>> from random import randint
  >>> L = [randint(10, 99) for _ in range(10)]
  >>> L
  [32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
  >>> 10 in L
  False
  >>> 81 in L
  True
  >>> L.index(81)
  3
  >>> L[3]
  81
  

  98. Nếu

  >>> from random import randint
  >>> L = [randint(10, 99) for _ in range(10)]
  >>> L
  [32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
  >>> 10 in L
  False
  >>> 81 in L
  True
  >>> L.index(81)
  3
  >>> L[3]
  81
  

  99, thì

  >>> from random import randint
  >>> L = [randint(10, 99) for _ in range(10)]
  >>> L
  [32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
  >>> 10 in L
  False
  >>> 81 in L
  True
  >>> L.index(81)
  3
  >>> L[3]
  81
  

  90
• Nếu

  >>> from random import randint
  >>> L = [randint(10, 99) for _ in range(10)]
  >>> L
  [32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
  >>> 10 in L
  False
  >>> 81 in L
  True
  >>> L.index(81)
  3
  >>> L[3]
  81
  

  91, thì hãy tìm trong nửa đầu của

  def linear_search(numbers, nbr):
      """
      Returns -1 if nbr belongs to numbers,
      else returns k for which numbers[k] == nbr.
      Items in the list numbers must be sorted
      in increasing order.
      """
      for i in range(len(numbers)):
          if numbers[i] == nbr:
              return i
          elif numbers[i] > nbr:
              return -1
      return -1
  

  1, đó là

  >>> from random import randint
  >>> L = [randint(10, 99) for _ in range(10)]
  >>> L
  [32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
  >>> 10 in L
  False
  >>> 81 in L
  True
  >>> L.index(81)
  3
  >>> L[3]
  81
  

  93
• Nếu

  >>> from random import randint
  >>> L = [randint(10, 99) for _ in range(10)]
  >>> L
  [32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
  >>> 10 in L
  False
  >>> 81 in L
  True
  >>> L.index(81)
  3
  >>> L[3]
  81
  

  94, thì hãy tìm kiếm trong nửa sau của

  def linear_search(numbers, nbr):
      """
      Returns -1 if nbr belongs to numbers,
      else returns k for which numbers[k] == nbr.
      Items in the list numbers must be sorted
      in increasing order.
      """
      for i in range(len(numbers)):
          if numbers[i] == nbr:
              return i
          elif numbers[i] > nbr:
              return -1
      return -1
  

  1, đó là

  >>> from random import randint
  >>> L = [randint(10, 99) for _ in range(10)]
  >>> L
  [32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
  >>> 10 in L
  False
  >>> 81 in L
  True
  >>> L.index(81)
  3
  >>> L[3]
  81
  

  96

Mã cho tìm kiếm nhị phân nằm trong chức năng bên dưới

>>> from random import randint
>>> L = [randint(10, 99) for _ in range(10)]
>>> L
[32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
>>> 10 in L
False
>>> 81 in L
True
>>> L.index(81)
3
>>> L[3]
81

9

Chúng tôi theo dõi tìm kiếm bằng cách * tích lũy độ sâu của đệ quy, * in bao nhiêu khoảng trắng theo độ sâu, * in danh sách còn lại để tìm kiếm trong

Để kiểm tra tìm kiếm, chúng tôi tạo một danh sách các số có 2 chữ số ngẫu nhiên

>>> from random import randint
>>> L = [randint(10, 99) for _ in range(10)]
>>> L
[32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
>>> 10 in L
False
>>> 81 in L
True
>>> L.index(81)
3
>>> L[3]
81

9

Nội trang

>>> from random import randint
>>> L = [randint(10, 99) for _ in range(10)]
>>> L
[32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
>>> 10 in L
False
>>> 81 in L
True
>>> L.index(81)
3
>>> L[3]
81

95 cũng không khai thác thứ tự. Hãy để chúng tôi xác định tìm kiếm chỉ mục cho danh sách được sắp xếp

>>> from random import randint
>>> L = [randint(10, 99) for _ in range(10)]
>>> L
[32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
>>> 10 in L
False
>>> 81 in L
True
>>> L.index(81)
3
>>> L[3]
81

9

Chúng tôi áp dụng cách chia để trị tương tự như trong

>>> from random import randint
>>> L = [randint(10, 99) for _ in range(10)]
>>> L
[32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
>>> 10 in L
False
>>> 81 in L
True
>>> L.index(81)
3
>>> L[3]
81

98, với sự chú ý bổ sung vào cách tính chỉ số

Mã để xác định chức năng

>>> from random import randint
>>> L = [randint(10, 99) for _ in range(10)]
>>> L
[32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
>>> 10 in L
False
>>> 81 in L
True
>>> L.index(81)
3
>>> L[3]
81

99 sau

$ python findsecret.py
Guess number in [0, 1000] : 500
Your guess is too low.
Guess number in [0, 1000] : 750
Your guess is too high.
Guess number in [0, 1000] : 625
Your guess is too high.
Guess number in [0, 1000] : 562
Your guess is too high.
Guess number in [0, 1000] : 531
Your guess is too high.
Guess number in [0, 1000] : 516
Your guess is too high.
Guess number in [0, 1000] : 508
Your guess is too high.
Guess number in [0, 1000] : 504
Your guess is too low.
Guess number in [0, 1000] : 506
found 506 after 9 guesses

2

Tìm kiếm chia đôi¶

Một vấn đề liên quan đến tìm kiếm nhị phân là tìm kiếm chia đôi, được sử dụng để đảo ngược một hàm. Ví dụ, hãy xem xét một hàm phân phối tích lũy, như trong Hình. 39 .

Hình. 39 Đảo ngược một hàm. đã cho $y = f(x)$, tìm $x$.

Dưới đây là báo cáo sự cố về đảo ngược hàm được lấy mẫu

\[\begin{split}\begin{array}{rcl} Đầu vào & \mbox{1. } & \mbox{mảng được lấy mẫu } \mbox{ giá trị hàm,} \\ & \mbox{2. } & \mbox{một giá trị hàm cụ thể } y = f(x). \\ Đầu ra & k. & A[k] \leq y \leq A[k+1]. \end{mảng}\end{split}\]

Chúng tôi làm việc với các mảng số được sắp xếp theo thứ tự tăng dần. Xem xét phiên Python tương tác bên dưới

$ python findsecret.py
Guess number in [0, 1000] : 500
Your guess is too low.
Guess number in [0, 1000] : 750
Your guess is too high.
Guess number in [0, 1000] : 625
Your guess is too high.
Guess number in [0, 1000] : 562
Your guess is too high.
Guess number in [0, 1000] : 531
Your guess is too high.
Guess number in [0, 1000] : 516
Your guess is too high.
Guess number in [0, 1000] : 508
Your guess is too high.
Guess number in [0, 1000] : 504
Your guess is too low.
Guess number in [0, 1000] : 506
found 506 after 9 guesses

3

Một tìm kiếm tuyến tính được cung cấp trong chức năng dưới đây

$ python findsecret.py
Guess number in [0, 1000] : 500
Your guess is too low.
Guess number in [0, 1000] : 750
Your guess is too high.
Guess number in [0, 1000] : 625
Your guess is too high.
Guess number in [0, 1000] : 562
Your guess is too high.
Guess number in [0, 1000] : 531
Your guess is too high.
Guess number in [0, 1000] : 516
Your guess is too high.
Guess number in [0, 1000] : 508
Your guess is too high.
Guess number in [0, 1000] : 504
Your guess is too low.
Guess number in [0, 1000] : 506
found 506 after 9 guesses

4

Tìm kiếm chia đôi trong một mảng sử dụng một hàm với nguyên mẫu sau

$ python findsecret.py
Guess number in [0, 1000] : 500
Your guess is too low.
Guess number in [0, 1000] : 750
Your guess is too high.
Guess number in [0, 1000] : 625
Your guess is too high.
Guess number in [0, 1000] : 562
Your guess is too high.
Guess number in [0, 1000] : 531
Your guess is too high.
Guess number in [0, 1000] : 516
Your guess is too high.
Guess number in [0, 1000] : 508
Your guess is too high.
Guess number in [0, 1000] : 504
Your guess is too low.
Guess number in [0, 1000] : 506
found 506 after 9 guesses

5

Chúng tôi có hai trường hợp cơ sở

1. Nếu

   >>> from random import randint
   >>> L = [randint(10, 99) for _ in range(10)]
   >>> L
   [32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
   >>> 10 in L
   False
   >>> 81 in L
   True
   >>> L.index(81)
   3
   >>> L[3]
   81
   

   90, thì

   >>> from random import randint
   >>> L = [randint(10, 99) for _ in range(10)]
   >>> L
   [32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
   >>> 10 in L
   False
   >>> 81 in L
   True
   >>> L.index(81)
   3
   >>> L[3]
   81
   

   91
2. Nếu

   >>> from random import randint
   >>> L = [randint(10, 99) for _ in range(10)]
   >>> L
   [32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
   >>> 10 in L
   False
   >>> 81 in L
   True
   >>> L.index(81)
   3
   >>> L[3]
   81
   

   92, thì

   >>> from random import randint
   >>> L = [randint(10, 99) for _ in range(10)]
   >>> L
   [32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
   >>> 10 in L
   False
   >>> 81 in L
   True
   >>> L.index(81)
   3
   >>> L[3]
   81
   

   93 nếu

   >>> from random import randint
   >>> L = [randint(10, 99) for _ in range(10)]
   >>> L
   [32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
   >>> 10 in L
   False
   >>> 81 in L
   True
   >>> L.index(81)
   3
   >>> L[3]
   81
   

   94, ngược lại thì

   >>> from random import randint
   >>> L = [randint(10, 99) for _ in range(10)]
   >>> L
   [32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
   >>> 10 in L
   False
   >>> 81 in L
   True
   >>> L.index(81)
   3
   >>> L[3]
   81
   

   91

Trong trường hợp chung, xác định

>>> from random import randint
>>> L = [randint(10, 99) for _ in range(10)]
>>> L
[32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
>>> 10 in L
False
>>> 81 in L
True
>>> L.index(81)
3
>>> L[3]
81

96

1. Nếu

   >>> from random import randint
   >>> L = [randint(10, 99) for _ in range(10)]
   >>> L
   [32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
   >>> 10 in L
   False
   >>> 81 in L
   True
   >>> L.index(81)
   3
   >>> L[3]
   81
   

   97, sau đó tìm kiếm trong

   >>> from random import randint
   >>> L = [randint(10, 99) for _ in range(10)]
   >>> L
   [32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
   >>> 10 in L
   False
   >>> 81 in L
   True
   >>> L.index(81)
   3
   >>> L[3]
   81
   

   98
2. Nếu

   >>> from random import randint
   >>> L = [randint(10, 99) for _ in range(10)]
   >>> L
   [32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
   >>> 10 in L
   False
   >>> 81 in L
   True
   >>> L.index(81)
   3
   >>> L[3]
   81
   

   99, sau đó tìm kiếm trong

   $ python findsecret.py
   Guess number in [0, 1000] : 500
   Your guess is too low.
   Guess number in [0, 1000] : 750
   Your guess is too high.
   Guess number in [0, 1000] : 625
   Your guess is too high.
   Guess number in [0, 1000] : 562
   Your guess is too high.
   Guess number in [0, 1000] : 531
   Your guess is too high.
   Guess number in [0, 1000] : 516
   Your guess is too high.
   Guess number in [0, 1000] : 508
   Your guess is too high.
   Guess number in [0, 1000] : 504
   Your guess is too low.
   Guess number in [0, 1000] : 506
   found 506 after 9 guesses
   

   20. Thêm

   $ python findsecret.py
   Guess number in [0, 1000] : 500
   Your guess is too low.
   Guess number in [0, 1000] : 750
   Your guess is too high.
   Guess number in [0, 1000] : 625
   Your guess is too high.
   Guess number in [0, 1000] : 562
   Your guess is too high.
   Guess number in [0, 1000] : 531
   Your guess is too high.
   Guess number in [0, 1000] : 516
   Your guess is too high.
   Guess number in [0, 1000] : 508
   Your guess is too high.
   Guess number in [0, 1000] : 504
   Your guess is too low.
   Guess number in [0, 1000] : 506
   found 506 after 9 guesses
   

   21 vào chỉ mục được trả về bởi lần tìm kiếm thứ 2

Mã cho hàm đệ quy bên dưới

>>> from random import randint
>>> L = [randint(10, 99) for _ in range(10)]
>>> L
[32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
>>> 10 in L
False
>>> 81 in L
True
>>> L.index(81)
3
>>> L[3]
81

0

Một ứng dụng của phép tìm chia đôi là bài toán tìm nghiệm

Cho f là hàm liên tục trên \([a,b]\) và . , then \(f(r) = 0\), for some \(r \in [a,b]\).

Các bước chính trong phương pháp chia đôi như sau

1. Hãy \(m = \frac{a+b}{2}\) .
2. Nếu \(f(a) f(m) < 0\) thì hãy thay thế . by \([a,m]\), otherwise replace \([a,b]\) by \([m,b]\).

Mỗi bước tăng một bit trong một gốc gần đúng r của f. Hàm

$ python findsecret.py
Guess number in [0, 1000] : 500
Your guess is too low.
Guess number in [0, 1000] : 750
Your guess is too high.
Guess number in [0, 1000] : 625
Your guess is too high.
Guess number in [0, 1000] : 562
Your guess is too high.
Guess number in [0, 1000] : 531
Your guess is too high.
Guess number in [0, 1000] : 516
Your guess is too high.
Guess number in [0, 1000] : 508
Your guess is too high.
Guess number in [0, 1000] : 504
Your guess is too low.
Guess number in [0, 1000] : 506
found 506 after 9 guesses

22 thực hiện một bước của phương pháp chia đôi

>>> from random import randint
>>> L = [randint(10, 99) for _ in range(10)]
>>> L
[32, 61, 50, 81, 30, 14, 53, 92, 22, 23]
>>> 10 in L
False
>>> 81 in L
True
>>> L.index(81)
3
>>> L[3]
81

1

Độ chính xác của gốc là

$ python findsecret.py
Guess number in [0, 1000] : 500
Your guess is too low.
Guess number in [0, 1000] : 750
Your guess is too high.
Guess number in [0, 1000] : 625
Your guess is too high.
Guess number in [0, 1000] : 562
Your guess is too high.
Guess number in [0, 1000] : 531
Your guess is too high.
Guess number in [0, 1000] : 516
Your guess is too high.
Guess number in [0, 1000] : 508
Your guess is too high.
Guess number in [0, 1000] : 504
Your guess is too low.
Guess number in [0, 1000] : 506
found 506 after 9 guesses

23. Đặt

$ python findsecret.py
Guess number in [0, 1000] : 500
Your guess is too low.
Guess number in [0, 1000] : 750
Your guess is too high.
Guess number in [0, 1000] : 625
Your guess is too high.
Guess number in [0, 1000] : 562
Your guess is too high.
Guess number in [0, 1000] : 531
Your guess is too high.
Guess number in [0, 1000] : 516
Your guess is too high.
Guess number in [0, 1000] : 508
Your guess is too high.
Guess number in [0, 1000] : 504
Your guess is too low.
Guess number in [0, 1000] : 506
found 506 after 9 guesses

24 là dung sai cho lỗi trên thư mục gốc. Nếu

$ python findsecret.py
Guess number in [0, 1000] : 500
Your guess is too low.
Guess number in [0, 1000] : 750
Your guess is too high.
Guess number in [0, 1000] : 625
Your guess is too high.
Guess number in [0, 1000] : 562
Your guess is too high.
Guess number in [0, 1000] : 531
Your guess is too high.
Guess number in [0, 1000] : 516
Your guess is too high.
Guess number in [0, 1000] : 508
Your guess is too high.
Guess number in [0, 1000] : 504
Your guess is too low.
Guess number in [0, 1000] : 506
found 506 after 9 guesses

25, trả lại

$ python findsecret.py
Guess number in [0, 1000] : 500
Your guess is too low.
Guess number in [0, 1000] : 750
Your guess is too high.
Guess number in [0, 1000] : 625
Your guess is too high.
Guess number in [0, 1000] : 562
Your guess is too high.
Guess number in [0, 1000] : 531
Your guess is too high.
Guess number in [0, 1000] : 516
Your guess is too high.
Guess number in [0, 1000] : 508
Your guess is too high.
Guess number in [0, 1000] : 504
Your guess is too low.
Guess number in [0, 1000] : 506
found 506 after 9 guesses

26 khác gọi lại

$ python findsecret.py
Guess number in [0, 1000] : 500
Your guess is too low.
Guess number in [0, 1000] : 750
Your guess is too high.
Guess number in [0, 1000] : 625
Your guess is too high.
Guess number in [0, 1000] : 562
Your guess is too high.
Guess number in [0, 1000] : 531
Your guess is too high.
Guess number in [0, 1000] : 516
Your guess is too high.
Guess number in [0, 1000] : 508
Your guess is too high.
Guess number in [0, 1000] : 504
Your guess is too low.
Guess number in [0, 1000] : 506
found 506 after 9 guesses

27. Phương pháp chia đôi đệ quy này được định nghĩa bên dưới