http___programarcadegames.com_index.php_chapter_searching_lang_tr_2.xml
1.1 2.1 3.1 3.2 4.1 4.2 4.3 5.1 6.1 6.2 7.1 8.1 8.2 9.1 10.1 11.1 12.1 13.1 14.1 15.1 16.1 16.2 16.3 17.1 17.2 17.3 17.4 17.5 17.6 18.1 18.2 18.3 18.4 18.5 19.1 19.2 19.3 19.4 19.5 19.6 19.7 19.8 20.1 21.1 21.2 21.3 21.4 21.5 21.6 22.1 23.1 24.1 24.2 25.1 26.1 26.2 27.1 27.2 28.1 28.2 29.1 30.1 31.1 32.1 33.1 34.1 34.2 34.3 34.4 35.1 36.1 37.1 37.2 37.3 38.1 38.2 38.3 38.4 38.5 38.6 39.1 39.2 40.1 41.1 41.2 41.3 41.4 42.1 43.1 43.2 43.3 43.4 43.5 44.1 45.1 45.2 46.1 46.2 46.3 47.1 47.2 47.3 48.1 49.1 49.2 49.3 50.1 50.2 51.1 51.2 51.3 51.4 51.5 52.1 52.2 52.3 53.1 54.1 54.2 54.3 55.1 55.2 56.1 57.1 57.2 58.1 58.2 59.1 59.2 60.1 61.1 62.1 63.1 64.1 65.1 65.2 65.3 65.4 66.1 67.1 67.2 67.3 67.4 67.5 68.1 68.2 69.1 69.2 69.3 69.4 69.5 69.6 70.1 71.1 71.2 71.3 72.1 73.1 74.1 75.1 76.1 77.1 78.1 79.1 80.1 81.1 82.1 83.1 84.1 84.2 84.3 84.4 84.5 85.1 86.1 87.1 87.2 88.1 92.1 93.1 93.2 93.3 94.1 95.1 95.2 96.1 99.1 99.2 99.3 100.1 101.1 101.2 101.3 102.1 103.1 103.2 104.1 104.2 104.3 104.4 104.5 104.6 104.7 105.1 105.2 105.3 105.4 106.1 106.2 106.3 106.4 107.1 108.1 109.1 110.1 111.1 113.1 114.1 114.2 115.1 116.1 117.1 118.1 119.1 120.1 121.1 122.1 123.1 124.1 125.1
Program Arcade GamesWith Python And Pygame Chapter 15: Searching Searching is an important and very common operation that computers do all the time. Searches are used every time someone does a ctrl-f for “find”, when a user uses “type-to” to quickly select an item, or when a web server pulls information about a customer to present a customized web page with the customer's order. There are a lot of ways to search for data. Google has based an entire multi-billion dollar company on this fact. This chapter introduces the two simplest methods for searching, the linear search and the binary search. 15.1 Reading From a File Before discussing how to search we need to learn how to read data from a file. Reading in a data set from a file is way more fun than typing it in by hand each time. Let's say we need to create a program that will allow us to quickly find the name of a super-villain. To start with, our program needs a database of super-villains. To download this data set, download and save this file: http://ProgramArcadeGames.com/chapters/16_searching/super_villains.txt These are random names generated by the nine.frenchboys.net website, although last I checked they no longer have a super-villain generator. Save this file and remember which directory you saved it to. In the same directory as super_villains.txt, create, save, and run the following python program: file = open("super_villains.txt") for line in file: print(line) There is only one new command in this code open. Because it is a built-in function like print, there is no need for an import. Full details on this function can be found in the Python documentation but at this point the documentation for that command is so technical it might not even be worth looking at. The above program has two problems with it, but it provides a simple example of reading in a file. Line 1 opens a file and gets it ready to be read. The name of the file is in between the quotes. The new variable file is an object that represents the file being read. Line 3 shows how a normal for loop may be used to read through a file line by line. Think of file as a list of lines, and the new variable line will be set to each of those lines as the program runs through the loop. Try running the program. One of the problems with the it is that the text is printed double-spaced. The reason for this is that each line pulled out of the file and stored in the variable line includes the carriage return as part of the string. Remember the carriage return and line feed introduced back in Chapter 1? The print statement adds yet another carriage return and the result is double-spaced output. The second problem is that the file is opened, but not closed. This problem isn't as obvious as the double-spacing issue, but it is important. The Windows operating system can only open so many files at once. A file can normally only be opened by one program at a time. Leaving a file open will limit what other programs can do with the file and take up system resources. It is necessary to close the file to let Windows know the program is no longer working with that file. In this case it is not too important because once any program is done running, the Windows will automatically close any files left open. But since it is a bad habit to program like that, let's update the code: file = open("super_villains.txt") for line in file: line = line.strip() print(line) file.close() The listing above works better. It has two new additions. On line 4 is a call to the strip method built into every String class. This function returns a new string without the trailing spaces and carriage returns of the original string. The method does not alter the original string but instead creates a new one. This line of code would not work: line.strip() If the programmer wants the original variable to reference the new string, she must assign it to the new returned string as shown on line 4. The second addition is on line 7. This closes the file so that the operating system doesn't have to go around later and clean up open files after the program ends. 15.2 Reading Into an Array It is useful to read in the contents of a file to an array so that the program can do processing on it later. This can easily be done in python with the following code: # Read in a file from disk and put it in an array. file = open("super_villains.txt") name_list = [] for line in file: line = line.strip() name_list.append(line) file.close() This combines the new pattern of how to read a file, along with the previously learned pattern of how to create an empty array and append to it as new data comes in, which was shown back in Chapter 7. To verify the file was read into the array correctly a programmer could print the length of the array: print( "There were",len(name_list),"names in the file.") Or the programmer could bring the entire contents of the array: for name in name_list: print(name) Go ahead and make sure you can read in the file before continuing on to the different searches. 15.3 Linear Search If a program has a set of data in an array, how can it go about finding where a specific element is? This can be done one of two ways. The first method is to use a linear search. This starts at the first element, and keeps comparing elements until it finds the desired element (or runs out of elements.) 15.3.1 Linear Search Algorithm # --- Linear search key = "Morgiana the Shrew" i = 0 while i < len(name_list) and name_list[i] != key: i += 1 if i < len(name_list): print( "The name is at position", i) else: print( "The name was not in the list." The linear search is rather simple. Line 4 sets up an increment variable that will keep track of exactly where in the list the program needs to check next. The first element that needs to be checked is zero, so i is set to zero. The next line is a bit more complex. The computer needs to keep looping until one of two things happens. It finds the element, or it runs out of elements. The first comparison sees if the current element we are checking is less than the length of the list. If so, we can keep looping. The second comparison sees if the current element in the name list is equal to the name we are searching for. This check to see if the program has run out of elements must occur first. Otherwise the program will check against a non-existent element which will cause an error. Line 6 simply moves to the next element if the conditions to keep searching are met in line 5. At the end of the loop, the program checks to see if the end of the list was reached on line 8. Remember, a list of n elements is numbered 0 to n-1. Therefore if i is equal to the length of the list, the end has been reached. If it is less, we found the element. 15.4 Variations On The Linear Search Variations on the linear search can be used to create several common algorithms. For example, say we had a list of aliens. We might want to check this group of aliens to see if one of the aliens is green. Or are all the aliens green? Which aliens are green? To begin with, we'd need to define our alien: class Alien: """ Class that defines an alien""" def __init__(self, color, weight): """ Constructor. Set name and color""" self.color = color self.weight = weight Then we'd need to create a function to check and see if it has the property that we are looking for. In this case, is it green? We'll assume the color is a text string, and we'll convert it to upper case to eliminate case-sensitivity. def has_property(my_alien): """ Check to see if an item has a property. In this case, is the alien green? """ if my_alien.color.upper() == "GREEN": return True else: return False 15.4.1 Does At Least One Item Have a Property? Is at least one alien green? We can check. The basic algorithm behind this check: def check_if_one_item_has_property_v1(my_list): """ Return true if at least one item has a property. """ i = 0 while i < len(my_list) and not has_property(my_list[i]): i += 1 if i < len(my_list): # Found an item with the property return True else: # There is no item with the property return False This could also be done with a for loop. In this case, the loop will exit early by using a return once the item has been found. The code is shorter, but not every programmer would prefer it. Some programmers feel that loops should not be prematurely ended with a return or break statement. It all goes to personal preference, or the personal preference of the person that is footing the bill. def check_if_one_item_has_property_v2(my_list): """ Return true if at least one item has a property. Works the same as v1, but less code. """ for item in my_list: if has_property(item): return True return False 15.4.2 Do All Items Have a Property? Are all aliens green? This code is very similar to the prior example. Spot the difference and see if you can figure out the reason behind the change. def check_if_all_items_have_property(my_list): """ Return true if at ALL items have a property. """ for item in my_list: if not has_property(item): return False return True 15.4.3 Create a List With All Items Matching a Property What if you wanted a list of aliens that are green? This is a combination of our prior code, and the code to append items to a list that we learned about back in Chapter 7. def get_matching_items(list): """ Build a brand new list that holds all the items that match our property. """ matching_list = [] for item in list: if has_property(item): matching_list.append(item) return matching_list How would you run all these in a test? The code above can be combined with this code to run: alien_list = [] alien_list.append(Alien("Green", 42)) alien_list.append(Alien("Red", 40)) alien_list.append(Alien("Blue", 41)) alien_list.append(Alien("Purple", 40)) result = check_if_one_item_has_property_v1(alien_list) print("Result of test check_if_one_item_has_property_v1:", result) result = check_if_one_item_has_property_v2(alien_list) print("Result of test check_if_one_item_has_property_v2:", result) result = check_if_all_items_have_property(alien_list) print("Result of test check_if_all_items_have_property:", result) result = get_matching_items(alien_list) print("Number of items returned from test get_matching_items:", len(result)) For a full working example see: programarcadegames.com/python_examples/show_file.php?file=property_check_examples.py These common algorithms can be used as part of a solution to a larger problem, such as find all the addresses in a list of customers that aren't valid. 15.5 Binary Search A faster way to search a list is possible with the binary search. The process of a binary search can be described by using the classic number guessing game “guess a number between 1 and 100” as an example. To make it easier to understand the process, let's modify the game to be “guess a number between 1 and 128.” The number range is inclusive, meaning both 1 and 128 are possibilities. If a person were to use the linear search as a method to guess the secret number, the game would be rather long and boring. Guess a number 1 to 128: 1 Too low. Guess a number 1 to 128: 2 Too low. Guess a number 1 to 128: 3 Too low. Guess a number 1 to 128: 93 Too low. Guess a number 1 to 128: 94 Correct! Most people will use a binary search to find the number. Here is an example of playing the game using a binary search: Guess a number 1 to 128: 64 Too low. Guess a number 1 to 128: 96 Too high. Guess a number 1 to 128: 80 Too low. Guess a number 1 to 128: 88 Too low. Guess a number 1 to 128: 92 Too low. Guess a number 1 to 128: 94 Correct! Each time through the rounds of the number guessing game, the guesser is able to eliminate one half of the problem space by getting a “high” or “low” as a result of the guess. In a binary search, it is necessary to track an upper and a lower bound of the list that the answer can be in. The computer or number-guessing human picks the midpoint of those elements. Revisiting the example: A lower bound of 1, upper bound of 128, mid point of $\dfrac{1+128}{2} = 64.5$. Guess a number 1 to 128: 64 Too low. A lower bound of 65, upper bound of 128, mid point of $\dfrac{65+128}{2} = 96.5$. Guess a number 1 to 128: 96 Too high. A lower bound of 65, upper bound of 95, mid point of $\dfrac{65+95}{2} = 80$. Guess a number 1 to 128: 80 Too low. A lower bound of 81, upper bound of 95, mid point of $\dfrac{81+95}{2} = 88$. Guess a number 1 to 128: 88 Too low. A lower bound of 89, upper bound of 95, mid point of $\dfrac{89+95}{2} = 92$. Guess a number 1 to 128: 92 Too low. A lower bound of 93, upper bound of 95, mid point of $\dfrac{93+95}{2} = 94$. Guess a number 1 to 128: 94 Correct! A binary search requires significantly fewer guesses. Worst case, it can guess a number between 1 and 128 in 7 guesses. One more guess raises the limit to 256. 9 guesses can get a number between 1 and 512. With just 32 guesses, a person can get a number between 1 and 4.2 billion. To figure out how large the list can be given a certain number of guesses, the formula works out like $n=x^{g}$ where $n$ is the size of the list and $g$ is the number of guesses. For example: $2^7=128$ (7 guesses can handle 128 different numbers) If you have the problem size, we can figure out the number of guesses using the log function. Specifically, log base 2. If you don't specify a base, most people will assume you mean the natural log with a base of $e \approx 2.71828$ which is not what we want. For example, using log base 2 to find how many guesses: Enough math! Where is the code? The code to do a binary search is more complex than a linear search: # --- Binary search key = "Morgiana the Shrew" lower_bound = 0 upper_bound = len(name_list)-1 found = False # Loop until we find the item, or our upper/lower bounds meet while lower_bound   key: upper_bound = middle_pos - 1 else: found = True if found: print( "The name is at position", middle_pos) else: print( "The name was not in the list." Since lists start at element zero, line 3 sets the lower bound to zero. Line 4 sets the upper bound to the length of the list minus one. So for a list of 100 elements the lower bound will be 0 and the upper bound 99. The Boolean variable on line 5 will be used to let the while loop know that the element has been found. Line 8 checks to see if the element has been found or if we've run out of elements. If we've run out of elements the lower bound will end up equaling the upper bound. Line 11 finds the middle position. It is possible to get a middle position of something like 64.5. It isn't possible to look up position 64.5. (Although J.K. Rowling was rather clever in enough coming up with Platform $9\frac{3}{4}$, that doesn't work here.) The best way of handling this is to use the // operator first introduced way back in Chapter 5. This is similar to the / operator, but will only return integer results. For example, 11 // 2 would give 5 as an answer, rather than 5.5. Starting at line 17 the program checks to see if the guess is high, low, or correct. If the guess is low, the lower bound is moved up to just past the guess. If the guess is too high, the upper bound is moved just below the guess. If the answer has been found, found is set to True ending the search. With the a list of 100 elements, a person can reasonably guess that on average with the linear search, a program will have to check 50 of them before finding the element. With the binary search, on average you'll still need to do about seven guesses. In an advanced algorithms course you can find the exact formula. For this course, just assume average and worst cases are the same. 15.6 Review 15.6.1 Multiple Choice Quiz Click here for a multiple-choice quiz. 15.6.2 Short Answer Worksheet Click here for the chapter worksheet. Click here for the chapter lab. You are not logged in. Log in here and track your progress. English version by Paul Vincent Craven Spanish version by Antonio Rodríguez Verdugo Russian version by Vladimir Slav Turkish version by Güray Yildirim Portuguese version by Armando Marques Sobrinho and Tati Carvalho Dutch version by Frank Waegeman Hungarian version by Nagy Attila Finnish version by Jouko Järvenpää French version by Franco Rossi Korean version by Kim Zeung-Il Chinese version by Kai Lin
1.1 2.1 3.1 4.1 5.1 6.1 7.1 8.1 9.1 10.1 11.1 12.1 13.1 14.1 15.1 16.1 17.1 18.1 19.1 20.1 21.1 22.1 23.1 24.1 25.1 26.1 27.1 28.1 29.1 30.1 31.1 32.1 33.1 34.1 35.1 36.1 37.1 38.1 39.1 41.1 42.1 43.1 44.1 45.1 46.1 47.1 48.1 49.1 50.1 51.1 52.1 53.1 54.1 55.1 56.1 57.1 58.1 59.1 60.1 61.1 62.1 63.1 64.1 65.1 66.1 67.1 68.1 69.1 70.1 71.1 72.1 73.1 74.1 75.1 76.1 78.1 79.1 80.1 81.1 82.1 83.1 84.1 85.1 86.1 87.1 88.1 89.1
Arcade Türü Oyun Programlamayıve Bilgisayar Bilimleri Öğrenin Chapter 16: Arama Arama, bilgisayarların her zaman yaptığı önemli ve çok yaygın uygulanan bir işlemdir. Aramalar her zaman ctrl-f kullanılarak yapılır, bir öğeyi çabucak seçmeyi sağlar ya da müşterinin siparişi ile ihtiyaca göre düzenlenen bir sayfaya bilgileri çekip müşteriye göstermek için kullanılır. Bilgiyi aramanın çok sayıda yolu vardır. Google bunun üzerine kurulmuş milyarlarca dolarlık bir şirkettir. Bu bölüm aramanın en basit iki yöntemi ile tanışmanızı sağlayacak. Bu yöntemler doğrusal ve bölerek aramalardır. 16.1 Bir Dosyadan Veri Okumak Nasıl arama yapılacağını tartışmadan önce, bir dosyadan verinin nasıl okunacağını bilmek kullanışlı olacaktır. Bu, programın geniş veri gruplarını kolayca aramasına izin verir. Diyelim ki süper güçlere sahip bir kötü adamın adını kolayca bulmamıza izin veren bir program oluşturmaya ihtiyacımız var. Başlamak için, programımız süper güçlere sahip kötü adamların veritabanına ihtiyaç duyar. Bu veri grubunu indirmek için alttaki linke sağ tıklayın: Süper Güçlere Sahip Kötü Adamlar ve example_sorted_names.txt dosyasını indirin. Bunlar ne yazık ki bunlar yazılırken yayında olmayan nine.frenchboys.net sitesi tarafından üretilmiş rastgele isimlerdir. Bu dosyayı kaydedin ve hangi dizine kaydettiğinizi unutmayın. Örnek isim listesinin kaydedildiği dizin ile aynı dizine alttaki Python programını oluşturun, kaydedin ve çalıştırın: file = open("example_sorted_names.txt") for line in file: print(line) Bu kodta yeni bir komut var. Python open isimli dahili bir fonksiyona sahiptir. Bu bir dahili (built-in) fonksiyon olduğu için, burada bir import işlemine gerek yoktur. Bu fonksiyon hakkında bütün detaylar Python dökümantasyonunda, burada, bulunabilir, fakat bu noktada bu komut için dökümantasyon çok fazla tekniktir ve bakmaya bile değmeyebilir. Üstteki programın iki sorunu var, fakat basit bir dosya okuma örneği sağlıyor. 1 numaralı satırda dosya açılıyor ve okumaya hazır hale getiriliyor. Dosyanın adı tırnak işaretleri içerisinde yer alıyor. Yeni file değişkeni okunacak dosyayı temsil eden bir nesne görevinde bulunuyor. 3. satır normal bir for döngüsünün bir dosyayı doğrudan satır satır nasıl okuyabileceğini gösteriyor. file değişkenini (metin dosyasını) satırların bir listesi olarak düşünün. Yeni line değişkeni program döngü boyunca çalışırken bu satırların her birinin değerine atanacak. Programı çalıştırmayı deneyin. Sorunlardan biri metnin çift aralıkla yazdırılmış olması. Bunun sebebi ise her satırın dosyadan ayrılıp saklandığı line değişkeninin satırbaşı işaretini (Ç.N "\n" içeriyor.) de stringin bir parçası olarak içermesi. print ifadesi ayrıca bir başka satırbaşı işareti ekliyor, sonuç olarak çıktıda iki aralık oluyor. İkinci problem ise dosya açılıyor, fakat kapatılmıyor. Bu problem çift aralık sorunu kadar açık değil, fakat önemli. Windows işletim sistemi birçok dosyayı tek bir kez açabilir. Aynı zamanda, bir dosyayı aynı anda sadece tek bir program açık tutabilir. Yani bir dosyayı açık bırakmak diğer programların bu dosya ile yapabileceği işlemlere kısıtlama koyar. Bu dosyayı kapatmak ve Windows'un programın bu dosya ile artık çalışmadığını bilmesini sağlamak gereklidir. Bu durumda bu işlem çok fazla önemli değildir çünkü bir program çalışmayı bitirdiğinde, Windows otomatik olarak açık kalan programları kapatır. Fakat bunu bu şekilde yapmak kötü bir alışkanlıktır ve sonuç olarak, kod güncellenmelidir. file = open("example_sorted_names.txt") for line in file: line=line.strip() print(line) file.close() Yukarıdaki listeleme daha iyi çalışıyor. İki yeni eklemeye sahip. 4. satırda yer alan strip metodu her stringden sondaki boşluğu ve satırbaşı işaretlerini siler. Bu metod orijinal stringi değiştirmek yerine bir kopyasını oluşturur. Bu satır çalışmayacaktır: line.strip() Programcı orijinal değişkenin yeni stringi belirtmesini istiyorsa, bu metodtan dönen yeni stringi ona atamalıdır. İkinci ekleme ise 7. satırda. Bu dosyayı işletim sisteminin daha sonra gitmek ve program bittikten sonra açık kalan dosyaları kapatmak zorunda kalmaması için kapatır. 16.2 Bir Dizinin İçerisine Okumak Bir dosyanın içeriğini programın daha sonra üzerinde işlem yapabilmesi için bir diziye okumak kullanışlıdır. Bu Python ile alttaki kod yardımıyla kolayca yapılabilir: # Diskten bir dosyayı oku ve onu bir dizinin içerisine koy. file = open("example_sorted_names.txt") name_list = [] for line in file: line=line.strip() name_list.append(line) file.close() Bu, dosyanın nasıl okunacağı ile ilgili model ile birlikte önceden öğrenilen boş bir dizinin nasıl oluşturulacağı ve ona yeni veri geldikçe nasıl ekleme yapılacağını birleştiriyor. Dosyanın bir dizinin içerisine doğru şekilde okunduğunu doğrulamak için programcı dizinin uzunluğunu ekrana yazdırabilir: print( "Bu dosyada",len(name_list),"tane isim var.") Ya da programcı dizinin bütün içeriğini ekrana yazdırabilir: for line in name_list: print(name) 16.3 Doğrusal Arama (Linear Search) Program bir veri grubuna bir dizinin içerisinde sahipse, özel bir öğeyi nasıl bulabilir? Bu iki yolla yapılabilir. İlk yöntem doğrusal arama kullanmaktır. Bu ilk öğeden başlar, istenen öğeye kadar elemanları karşılaştırmaya istenen elemanı bulana kadar devam eder ya da kontrol edilecek elemanları bitirir. # Doğrusal arama i=0 while i < len(name_list) and name_list[i] != "Morgiana the Shrew": i += 1 if i == len(name_list): print( "İsim listede bulunamadı." ) else: print( "İsmin bulunduğu pozisyon:",i) Doğrusal arama oldukça kolaydır. 2. satırda programın bir sonraki kontrol edeceği liste elemanının tam olarak nerede olduğu takip edilsin diye bir artış değişkeni belirlenmiştir. Kontrol edilmeye ihtiyaç duyan ilk eleman sıfırıncı elemandır, bu durumda i de sıfır olarak ayarlanmıştır. Sonraki satır biraz daha karmaşıktır. Bilgisayar iki şey gerçekleşene kadar döngüye devam edecektir. Aranan elemanı bulması ya da elemanların bitmesi. İlk karşılaştırma kontrol ettiğimiz elemanın indisi listenin uzunluğundan küçük mü diye bakıyor. Eğer küçükse, döngüye devam ediyor. İkinci karşılaştırma listedeki geçerli eleman aradığımız isme eşit mi diye bakıyor. Programın kontrol edeceği elemanların bitip bitmediğinin kontrolü ilk önce yapılmak zorundadır. Aksi takdirde, program var olmayan bir elemanı kontrol etmeye çalışacak ve bu da bir hata oluşturacaktır. 4. satır 3. satırda belirtilen aramaya devam etme kriterleri sağlanıyorsa basitçe sonraki öğeye gidiyor. Döngünün sonunda, program listenin sonuna erişilip erişilmediğini 6. satırda kontrol ediyor. Unutmayın, n elemanlı bir liste 0'dan n-1'e kadar numaralandırılır. Bu nedenle, eğer i, n. pozisyona(listenin uzunluğu) bakması için ayarlandıysa listenin sonuna erişilmiştir. Programın doğrusal arama kullandığını varsayarak alttakileri cevaplayın: - Liste n elemana sahipse, en iyi durumda bilgisayar istenen elemanı bulmadan önce kaç elemanı kontrol etmeye ihtiyaç duyar? - Liste n eleman içeriyorsa, en kötü durumda bilgisayar istenen elemanı bulmadan önce kaç elemanı kontrol etmeye ihtiyaç duyar? - Liste n elemandan oluşuyorsa, istenen elemanın listede olmadığını belirlemek için kaç elemanın kontrol edilmesine ihtiyaç vardır? - Listede n eleman varsa, istenen eleman bulunmadan önce bilgisayarın kontrol etmesi gereken elemanların ortalama sayısı nedir? - Örnek doğrusal arama kodunu alın ve onu bir fonksiyona koyun. İstenen elemanla birlikte bir liste alın. Elemanın yerini döndürün veya bulunamazsa -1 döndürün. 16.4 Bölerek Arama Bir listede arama yapmanın daha hızlı bir yolu bölerek arama ile mümkündür. Bölerek aramadaki işlem klasik sayı tahmin oyunu olan "1 ile 100 arasında bir sayı tahmin et" örneği ile tarif edilebilir. İşlemi anlamayı daha basit hale getirmek için, oyunu "1 ile 128 arasında bir sayı tahmin edin" şekline getirelim. Sayı aralığı kapalıdır, yani hem 1 hem de 128 ihtimallere dahildir. Eğer bir kişi doğrusal aramayı gizli bir sayıyı tahmin etmek için yöntem olarak kullanırsa, oyun oldukça uzun ve sıkıcı olurdu. 1'den 128'e kadar bir sayı tahmin et: 1 Çok az. 1'den 128'e kadar bir sayı tahmin et: 2 Çok az. 1'den 128'e kadar bir sayı tahmin et: 3 Çok az. .... 1'den 128'e kadar bir sayı tahmin et: 93 Çok az. 1'den 128'e kadar bir sayı tahmin et: 94 Doğru! Çoğu kişi bir sayıyı bulmak için bölerek aramayı kullanacaktır. Burda bölerek arama kullanarak bu oyunu oynamanın bir örneği var: 1'den 128'e kadar bir sayı tahmin et: 64 Çok az. 1'den 128'e kadar bir sayı tahmin et: 96 Çok fazla. 1'den 128'e kadar bir sayı tahmin et: 80 Çok az. 1'den 128'e kadar bir sayı tahmin et: 88 Çok az. 1'den 128'e kadar bir sayı tahmin et: 92 Çok az. 1'den 128'e kadar bir sayı tahmin et: 94 Doğru! Sayı tahmin oyununun her aşamasında, tahmin eden kişi problem alanının yarısını "fazla" ya da "az" olarak aldığı tahmin cevabıyla eleyebiliyor. Bölerek aramada, cevabın olabileceği listede bir üst ve alt sınır takip etmek gereklidir. Bilgisayar veya sayı tahmin eden insan bu öğelerin orta noktasını alır. Örneğe tekrar bakalım: Bir alt sınır 1, üst sınır 128, orta noktaları $(1+128)/2 = 64.5$. 1'den 128'e kadar bir sayı tahmin et: 64 Çok az. Bir alt sınır 65, üst sınır 128, orta noktaları $(65+128)/2 = 96.5$. 1'den 128'e kadar bir sayı tahmin et: 96 Çok fazla. Bir alt sınır 65, üst sınır 95, orta noktaları $(65+95)/2 = 80$. 1'den 128'e kadar bir sayı tahmin et: 80 Çok az. Bir alt sınır 81, üst sınır 95, orta noktaları $(81+95)/2 = 88$. 1'den 128'e kadar bir sayı tahmin et: 88 Çok az. Bir alt sınır 89, üst sınır 95, orta noktaları $(89+95)/2 = 92$. 1'den 128'e kadar bir sayı tahmin et: 92 Çok az. Bir alt sınır 93, üst sınır 95, orta noktaları $(93+95)/2 = 94$. 1'den 128'e kadar bir sayı tahmin et: 94 Doğru! Bölerek arama(ikili arama) önemli derecede daha az tahmin gerektirir. En kötü durumda, 1 ile 128 arasında bir sayıyı 7 kerede bulabilir. Bir deneme fazla yapmak bu limiti 256'ya çıkarır. 9 deneme ile bu sayı 1 ile 512 arasına çıkar. Sadece 32 denemede, bir kişi 1 ile 4.2 milyar arasındaki sayıyı doğru tahmin edebilir. Bölerek aramanın kodu doğrusal aramadan biraz daha karmaşıktır: # Bölerek arama desired_element = "Morgiana the Shrew"; lower_bound = 0 upper_bound = len(name_list)-1 found = False while lower_bound   desired_element: upper_bound = middle_pos else: found = True if found: print( "İsmin bulunduğu indis",middle_pos) else: print( "İsim listede bulunamadı." ) Listeler sıfır indisinden başladığı için, 3. satırda alt satır sıfır olarak belirleniyor. 4. satır üst sınırı listenin uzunluğunun bir eksiği olarak belirliyor. Şimdiye kadar 100 elemandan oluşan listenin alt sınırı 0, üst sınırı 99 oluyor. 5. satırdaki mantıksal(Boolean) değişken while döngüsüne elemanın bulunduğunu söylemek için kullanılıyor. 6. satırda elemanın bulunup bulunmadığı veya bütün elemanların bitip bitmediği kontrol ediliyor. Eğer elemanlar bittiyse alt sınır üst sınıra eşitleniyor. 7. satırda orta nokta bulunuyor. 64.5 gibi bir orta nokta bulmak da mümkün. 64.5 pozisyonuna bakmak imkansız. (J.K. Rowling'in Platform $9\frac{3}{4}$'de oldukça akıllıca yaklaşmasına rağmen.) Bu nedenle sonucu (int) ile tamsayıya çevirmek gerekiyor. Bu satırı yapmanın alternatif bir yolu // operatörünü kullanmak. Bu / operatörüne benzerdir, fakat sadece tamsayı olarak sonuç döndürür. Örneğin, 11 // 2 cevap olarak 5.5 yerine 5'i cevap olarak verecektir. middle_pos = (lower_bound+upper_bound) // 2 8. satırdan başlayarak, program tahminin yüksek, düşük veya doğru olup olmadığını kontrol etmeye başlıyor. Eğer tahmin düşükse, alt sınır son tahminin hemen üstüne yükseltiliyor. Eğer tahmin düşükse, üst sınır tahminin hemen altına düşürülüyor. Cevap bulunduysa, found değişkenine True atanıyor ve arama bitiyor. Alttakileri cevaplayın, programın bölerek aramayı kullandığını ve listelerin sıralı olduğunu varsayın: - Listede n eleman varsa, en iyi durumda bilgisayar istenen elemanı bulmadan önce kaç eleman kontrol edilecektir? - Listede n eleman varsa, en kötü durumda bilgisayar istenen elemanı bulmadan önce kaç eleman kontrol edilecektir? - Listede n eleman varsa, bilgisayar istenen elemanın listede olmadığını belirlemek için kaç eleman kontrol edilmelidir? - Listede n eleman varsa, durumda bilgisayar istenen elemanı bulmadan önce ortalama kaç tane eleman kontrol edilecektir? - Doğrusal arama kodu örneğini alın ve onu bir fonksiyonun içerisine koyun. Listeyi istenen elemanla birlikte gönderin. Elemanın indisini döndürsün veya bulunamazsa -1 döndürsün. You are not logged in. Log in here and track your progress. English version by Paul Vincent Craven Russian version by Vladimir Slav Turkish version by Güray Yildirim Dutch version by Frank Waegeman Portuguese version by Tati Carvalho