262 Arrays Chapter 7 peated in one quarter (Space web hosting)
262 Arrays Chapter 7 peated in one quarter of the original array. The search continues until the search key is equal to the middle element of a subarray, or until the subarray consists of one element that is not equal to the search key (i.e., the search key is not found). In a worst-case scenario, searching an array of 1024 elements will take only 10 comparisons by using a binary search. Repeatedly dividing 1024 by 2 (after each comparison we eliminate from consideration half the array) yields the values 512, 256, 128, 64, 32, 16, 8, 4, 2 and 1. The number 1024 (210) is divided by 2 only ten times to get the value 1. Dividing by 2 is equivalent to one comparison in the binary search algorithm. An array of 1,048,576 (220) elements takes a maximum of 20 comparisons to find the key. An array of one billion elements takes a maximum of 30 comparisons to find the key. This is a tremendous increase in performance over the linear search, which required comparing the search key with an average of half the elements in the array. For a one-billion-element array, the difference is between an average of 500 million comparisons and a maximum of 30 comparisons! The maximum number of comparisons needed for the binary search of any sorted array is the exponent of the first power of 2 greater than the number of elements in the array. Figure 7.12 presents the iterative version of method BinarySearch (lines 59 85). The method receives two arguments an integer array called array (the array to search) and an integer key (the search key). The array is passed to BinarySearch even though the array is an instance variable of the class. Once again, this is done because an array normally is passed to a method of another class for searching. Line 67 calculates the middle element of the array being searched by determining the number of elements in the array and dividing this value by 2. Recall that using the / operator with integers performs an integer division, which truncates the result. So, when there is an even number of elements in the array there is no middle element the middle of our array is actually between two elements. When this occurs, the calculation on line 67 returns the smaller index of the two middle elements. 1 // Fig. 7.12: BinarySearchTest.cs 2 // Demonstrating a binary search of an array. 3 4 using System; 5 using System.Drawing; 6 using System.Collections; 7 using System.ComponentModel; 8 using System.Windows.Forms; 9 using System.Data; 10 11 public class BinarySearchTest : System.Windows.Forms.Form 12 { 13 private System.Windows.Forms.Label promptLabel; 14 15 private System.Windows.Forms.TextBox inputTextBox; 16 17 private System.Windows.Forms.Label resultLabel; 18 private System.Windows.Forms.Label displayLabel; 19 private System.Windows.Forms.Label outputLabel; 20 21 private System.Windows.Forms.Button findButton; 22 Fig. 7.12 Binary search of a sorted array. (Part 1 of 4.)
We would like to recommend you tested and proved virtual web hosting services, which you will surely find to be of great quality.