Binary Searching Array Element
Let DATA be the following sorted 13-element array:
DATA: 11, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 88, 99
We apply the binary search to DATA for different values of ITEM.
(a) Suppose ITEM = 40. The search for ITEM in the array DATA is pictured in fig. 4.6, Where the values of DATA[BEG] and DATA[END] in each stage of the algorithm are indicated by circles and the value of DATA[MID] by a square.Specifically, BEG, END and MID will have the following succesive values:
1. Initially, BEG = 1 and END = 13. Hence
MID = INT[(1 + 13/2)] = 7 and so DATA[MID] = 55
2. Since 40 < 55, End has its value changed by END = MID - 1 = 6. Hence
MID = INT[(1+6/2)] = 3 and so DATA[MID] = 30
3. Since 40 > 30, BEG has its value changes by BEG = MID + 1 = 4. Hence
MID = INT[(4+6)/2] = 5 and so DATA[MID] = 40
We have found ITEM in location LOC = MID = 5.
(b) Suppose ITEM = 85. The Binary search for ITEM in the array DATA is pictured in fig. 4.6, Where the values of DATA[BEG] and DATA[END] in each stage of the algorithm are indicated by circles and the value of DATA[MID] by a square.Specifically, BEG, END and MID will have the following succesive values:
1. Initially, BEG = 1 and END = 13. Hence
MID = INT[(1 + 12)/2] = 7 and so DATA[MID] = 55
2. Since 85 > 55, End has its value changed by END = MID + 1 = 8. Hence
MID = INT[(8 + 13)/2] = 10 and so DATA[MID] =77
3. Since 85 > 77, BEG has its value changes by BEG = MID + 1 = 11. Hence
MID = INT[(11 + 13)/2] = 12 and so DATA[MID] = 88.
4. Since 85 < 88, END has its value changes by END = MID - 1 = 11. Hence
MID = INT[(11 + 11)/2] = 11 and so DATA[MID] = 80
Binary Search of ITEM = 85.
If You want to learn about the technology, computer science & engineering, web programming, freelancing, earning please click here :CSE SOLVE
Let DATA be the following sorted 13-element array:
DATA: 11, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 88, 99
We apply the binary search to DATA for different values of ITEM.
(a) Suppose ITEM = 40. The search for ITEM in the array DATA is pictured in fig. 4.6, Where the values of DATA[BEG] and DATA[END] in each stage of the algorithm are indicated by circles and the value of DATA[MID] by a square.Specifically, BEG, END and MID will have the following succesive values:
1. Initially, BEG = 1 and END = 13. Hence
MID = INT[(1 + 13/2)] = 7 and so DATA[MID] = 55
2. Since 40 < 55, End has its value changed by END = MID - 1 = 6. Hence
MID = INT[(1+6/2)] = 3 and so DATA[MID] = 30
3. Since 40 > 30, BEG has its value changes by BEG = MID + 1 = 4. Hence
MID = INT[(4+6)/2] = 5 and so DATA[MID] = 40
We have found ITEM in location LOC = MID = 5.
11, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 88, 99
11, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 88, 99
11, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 88, 99 [Successful]
(b) Suppose ITEM = 85. The Binary search for ITEM in the array DATA is pictured in fig. 4.6, Where the values of DATA[BEG] and DATA[END] in each stage of the algorithm are indicated by circles and the value of DATA[MID] by a square.Specifically, BEG, END and MID will have the following succesive values:
1. Initially, BEG = 1 and END = 13. Hence
MID = INT[(1 + 12)/2] = 7 and so DATA[MID] = 55
2. Since 85 > 55, End has its value changed by END = MID + 1 = 8. Hence
MID = INT[(8 + 13)/2] = 10 and so DATA[MID] =77
3. Since 85 > 77, BEG has its value changes by BEG = MID + 1 = 11. Hence
MID = INT[(11 + 13)/2] = 12 and so DATA[MID] = 88.
4. Since 85 < 88, END has its value changes by END = MID - 1 = 11. Hence
MID = INT[(11 + 11)/2] = 11 and so DATA[MID] = 80
11, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 88, 99
11, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 88, 99
11, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 88, 99
11, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 88, 99 [Unsuccessful]
Binary Search of ITEM = 85.
Posts
0 comments:
Post a Comment