第20題 Element Search(元素搜索) <<
Previous Next >> 解答-2
題目-2
Exercise 20
Write a function that takes an ordered list of numbers (a list where the elements are in order from smallest to largest) and another number. The function decides whether or not the given number is inside the list and returns (then prints) an appropriate boolean.
Extras:
Discussion
Topics:
- Booleans - True and False
- Equality testing
- Binary search
Booleans
When you are writing programs, there is often a time when you need to make a decision about something based on the truthfulness of something else. Basically, you need to make a decision based on whether something is TRUE or something is FALSE.
An obvious example is when using conditionals:
(We talked about this idea of conditionals in a previous post.)
But what is happening behind the scenes is that the statement michele_age > 17
is being evaluated into a type that is either True
or False
. This is then getting stored inside the variable truth_value
, and then the decision is being made inside the conditional.
Here is another example:
What the while True
statement does at the beginning of the code segment is continue asking for an age and printing a response - it never stops. (To stop it, press CTRL-C in a terminal or in the Python shell).
These types - True
and False
are called boolean types or boolean variables. They can only take on two values, either True
or False
.
For more extensive reading on Python booleans, take a look at these resources.
Equality testing on strings
Scenarios come up where you need to test if things are equal to each other - numbers or strings or something else. We covered this idea in a previous post, but it is worth returning to again, this time for strings.
Good thing it’s easy!
Remember, comparing numbers for equality is done with an ==
sign, like so:
Turns out, comparing strings is equally (hehe..) simple, using a ==
to check for equality and !=
to check for inequality.
Or, a more practical password-checking piece of code:
Binary search
There are a number of ways to search for elements in a list, and there is no one correct way to do so. The point of this exercise is to get you thinking about possible ways to search for elements in the list, in an entire sequence of exercises about lists, searching, and sorting. This exercise might seem silly and easy at first, but the more you dive into this topic, the more difficult it becomes.
The word “binary” means there are two choices (in computers, often this is 0 or 1, but it really means any choice between two things). “Search” is to look for something. So the main idea behind binary search is to look for something in a way that gives you a decision tree for where to look, containing two choices. Let me give you an example:
Let’s take the list a = [1, 3, 5, 30, 42, 43, 500]
. It is an “ordered list”, or a list where the elements in the list go from smaller to larger. Let’s say we want to know whether the element 9
is in the list or not. Here is what we do:
- Look at the middle element in the list - it is ‘30’. * ‘9 < 30’, so let us ignore the elements to the right of ‘30’.
- The new list we are looking at is now
[1, 3, 5]
.
- Look at the middle element in this new list - it is
3
.
- ‘9 > 3’, so ignore the elements to the left of
3
.
- The new list we are looking at is
[5]
.
- The list has one element and it is not
9
.
9
is not in the list.
What the example shows is that in an ordered list, knowing how the element you are looking for compares to another element in the list splits the list in two - one half where the element can be, and one where it definitely cannot be. In the case where our list contains millions of elements, knowing that we can cut the “search space” in half is a great increase in efficiency.
When you are writing the solution, first try to write it without binary search. Then when you want to try implementing binary search, write a separate function. In the solution I will give an example for how to write a binary search in Python.
練習20
編寫一個函數,該函數接受一個有序的數字列表(一個元素從最小到最大的順序列表)和另一個數字。該函數確定給定的數字是否在列表中,並返回(然後打印)適當的布爾值。
附加功能:
討論區
主題:
- 布爾值-對與錯
- 平等測試
- 二進制搜索
布爾值
在編寫程序時,通常會需要根據其他事物的真實性來做出決策。基本上,您需要根據某物是TRUE還是FALSE來做出決定。
一個明顯的例子是使用條件句時:
(我們在上一篇文章中討論了這種有條件的想法。)
但是幕後發生的事情是該語句michele_age > 17
正在被評估為True
or或類型False
。然後將其存儲在變量中truth_value
,然後在條件中進行決策。
這是另一個示例:
該while True
語句在代碼段開頭的作用是繼續詢問年齡並打印響應-它永遠不會停止。(要停止它,請在終端或Python Shell中按CTRL-C)。
這些類型的-True
和False
被稱為布爾類型或布爾變量。它們只能採用True
或的兩個值False
。
要更廣泛地了解Python布爾值,請查看這些 資源。
字符串相等性測試
在場景中,您需要測試事物是否彼此相等-數字或字符串或其他。我們在上一篇文章中介紹了這個想法,但是這次還是值得再來一次。
好東西很容易!
請記住,比較數字是否相等是用一個==
符號完成的,如下所示:
事實證明,使用a==
來檢查相等性和!=
檢查不相等性,比較字符串同樣(嘿,..)很簡單。
或者,使用更實用的密碼檢查代碼:
二進制搜索
有多種方法可以搜索列表中的元素,但沒有一種正確的方法可以搜索列表中的元素。該練習的目的是讓您思考有關列表,搜索和排序的整個練習序列中搜索列表中元素的可能方法。剛開始時,此練習可能看起來很愚蠢且容易,但是您越深入該主題,就越困難。
“二進制”一詞表示有兩種選擇(在計算機中,通常是0或1,但實際上表示在兩種情況之間可以選擇)。“搜索”是尋找東西。因此,二進制搜索背後的主要思想是以某種方式尋找事物,該決策樹為您提供尋找位置的決策樹,其中包含兩個選擇。讓我舉一個例子:
讓我們看一下清單a = [1, 3, 5, 30, 42, 43, 500]
。它是一個“有序列表”,或者是列表中元素從小到大的列表。假設我們想知道元素9
是否在列表中。這是我們的工作:
- 查看列表中的中間元素-它是“ 30”。*'9 <30',因此讓我們忽略'30'右邊的元素。
- 現在我們正在查看的新列表
[1, 3, 5]
。
- 看一下這個新列表的中間元素-是
3
。
- '9> 3',因此忽略左側的元素
3
。
- 我們正在查看的新列表是
[5]
。
- 該列表只有一個元素,而沒有
9
。
9
不在列表中。
該示例顯示的是,在有序列表中,知道要查找的元素與列表中另一個元素的比較方式,將列表分為兩部分-元素可以位於其中一半,而絕對不能位於其中。在我們的列表包含數百萬個元素的情況下,知道我們可以將“搜索空間”減少一半,這將大大提高效率。
在編寫解決方案時,請首先嘗試在不進行二進制搜索的情況下編寫它。然後,當您想嘗試實現二進制搜索時,編寫一個單獨的函數。在解決方案中,我將給出一個示例,說明如何使用Python編寫二進制搜索。
第20題 Element Search(元素搜索) <<
Previous Next >> 解答-2