The Self-Taught Computer Scientist
Download 1.48 Mb. Pdf ko'rish
|
books-library.net-11301817Az7X6
2 x 2 x 2 = 8
3 log 2 (8) = 3 Base Figure 3.6: Exponential notation versus logarithmic notation Introduction to Algorithms 32 In this case, bisect_left returned 1 because 'banana' is at index 1 in sorted_fruits . If the item you are looking for is not in your sorted iterable, bisect_left returns where it would be if it were there. from bisect import bisect_left sorted_fruits = ['apple', 'banana', 'orange', 'plum'] bisect_left(sorted_fruits, 'kiwi') >> 2 As you can see, 'kiwi' is not in your sorted iterable, but if it were, it would be at index 2. Because bisect_left tells you where an item should go if it isn’t there, to check if an item is in an iterable, you need to see if the index is within the iterable ( bisect could return a position outside of your iterable) and if the item at the index bisect_left returns is the value you are looking for. Here is how to use bisect_left to perform a binary search in Python: from bisect import bisect_left def binary_search(an_iterable, target): index = bisect_left(an_iterable, target) if index <= len(an_iterable) and an_iterable[index] == target: return True return False If bisect_left returns an index within your iterable and that index contains your target, you return True because the item is in your iterable. Otherwise, it is not, and you return False . Searching for Characters You know how to search for characters in a list using Python’s built- in linear and binary search tools. But what if you had to write a linear or binary search from scratch to search for characters instead of numbers? To understand how to search for characters, you need to understand more about how a computer stores them. A character set is a map between characters and binary numbers. Computer scientists use character encoding to implement different character sets. In American Standard Code for Information Interchange (ASCII), your computer maps each letter of the alphabet to a seven- bit number. Figure 3.7 shows the relationship between binary and the different characters in the English language. For example, the ASCII value of A is 1000001 in binary (you will learn more about binary later in the book) and 65 in base 10 (the number system you use every day). The binary digit for b is 01100010. Uppercase letters, lowercase letters, punctuation symbols, numerals, and various control characters that indicate actions, such as page breaks and line feeds, all have ASCII codes. There are ASCII codes |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling