Homework SourseWith the help of an example in c prove how a binary search c
With the help of an example in c++, prove how a binary search can prove to be more efficient than a sequential search for an array of 10 sorted numbers.
Solution
To analyze the binary search algorithm, we need to recall that each comparison eliminates about half of the remaining items from consideration. What is the maximum number of comparisons this algorithm will require to check the entire list? If we start with n items, about n2n2 items will be left after the first comparison. After the second comparison, there will be about n4n4. Then n8n8, n16n16, and so on. How many times can we split the list? Table 3 helps us to see the answer.
Comparisons Approximate Number of Items Left
1 n2n2
2 n4n4
3 n8n8
...
i n2i
When we split the list enough times, we end up with a list that has just one item. Either that is the item we are looking for or it is not. Either way, we are done. The number of comparisons necessary to get to this point is i where n2i=1n2i=1. Solving for i gives us i=logni=logn. The maximum number of comparisons is logarithmic with respect to the number of items in the list. Therefore, the binary search is O(logn)O(logn).
One additional analysis issue needs to be addressed. In the recursive solution shown above, the recursive call,
binarySearch(alist[:midpoint],item)
Binary Search
Compare x with the middle name in the book. If x comes before y,
recursively look for x in the first half. Otherwise recursively look
for x in the second half. The search is finished when the beginning
and end of the list are within one.
Example
Suppose our book, b, contains these n (8) names, and we are looking for
the name, x, which is \"helen.\" Suppose that each name has a
corresponding phone number, although the numbers are not shown here.
begin mid end
0 1 2 3 4 5 6 7
[ anna carl doug earl fiona gerard helen zack ]
begin mid end
begin mid end
begin end
We find \"helen\" in 3 steps with the binary search, whereas it would have
taken 7 steps with the linear search. [log2n = log28 = 3]
The number of times you go through the loop is proportional to the
number of times you have to divide the list of size n by 2 in order to
reduce it to a list that has begin and end within one ... log base 2 of n.
How much time does this take? (Depends on how it\'s implemented.)
Best case: log2n steps (could be 1 step)
Average case: log2n steps (could be log2n / 2 steps)
Worse case: log2n steps
Assume that we have an array book of phone book entries (name & number),
and we are searching for the phone number for the name x. Here is a
version of the binary search that initializes the counters for begin and
end to the first and last indices in the array.
// Initialization
int mid;
int begin = 0;
int end = book.length-1;
// Loop until begin and end are within 1.
while (begin != end-1) {
mid = (begin+end)/2;
if (book[mid].getName().compareTo(x) > 0)
end = mid;
else
begin = mid;
}
// Print phone number found
if (book[begin].getName().equals(x))
System.out.println (\"Found \" + book[begin].getNum());
else
System.out.println (\"Value not found.\");
Note that this algorithm has a bug when you search for something that
is contained in the last index of the array, or if you search for
something that is bigger than the last value in the array. The
algorithm returns the second last index in the array. We end up with
begin=N-2 and end=N-1 because the algorithm ends as soon as begin and
end are within one.
Next we\'ll look at an algorithm that eliminates this problem. It will
initialize begin to one smaller (-1) and end to one larger (N). If the
element is in the last index of the array, the algorithm will finish
with begin=N-1 and end=N (begin contains the value we are searching
for).
Binary Search
Search an array of integers.
public class BinarySearch {
public static void main (String[] args) {
int[] list = {3,4,6,7,9,10,12,13,15};
System.out.println (search (12, list)); // 6
System.out.println (search ( 7, list)); // 3
System.out.println (search ( 2, list)); // -1
System.out.println (search (20, list)); // 8
}
// Return the index of the last element in list
// less than or equal to s.
public static int search (int s, int[] list) {
int begin = -1; // start index
int end = list.length; // end index
// Inv: list[0..begin]<=s && list[end..N-1]>s &&
// -1<=begin<end<=N (Note: N is list.length)
while (begin != end-1) {
int m = (begin+end) / 2;
if (list[m] > s) {
end = m;
} else {
begin = m;
}
}
return begin;
}
}
Tracing Binary Search
Search key: 12
3 4 6 7 9 10 12 13 15
-1 0 1 2 3 4 5 6 7 8 9
b e
m
Search key: 7
3 4 6 7 9 10 12 13 15
-1 0 1 2 3 4 5 6 7 8 9
b e
m
We use \"order of\" (or Big-Oh notation) to express the time complexity
of an algorithm. This in an approximation of the time that it takes to
run.
Suppose that you are comparing two different algorithms that solve a
particular problem. One has a worse case complexity of n+1
comparisons, and the other has a worse case complexity of n+3. What
does this mean in terms of Big-Oh?
We want to compare algorithms, as our data set gets really large (as n
increases). Which of these are faster?
n + 1 <==> n + 3 --> both are O(n)
n <==> 2n --> both are O(n)
n <==> n2 --> left is O(n), right is O(n2)
n2 + n <==> n2 + 300 --> both are O(n2)
We use Big-Oh notation to give a rough estimate of the complexity.
This is usually sufficient. We remove the additive and multiplicative
factors from the expression, and say that the complexity of the
algorithm is \"on the order of\" some expression containing n.
If you count the number of operations in an algorithm, and get the
following number of comparisons, what would the complexity be?
5n comparisons --> O(n)
n + 10 comparisons --> O(n)
0.6n + 33 comparisons --> O(n)
5 comparisons --> O(1)
log2n + 1 comparisons --> O(log2n)
2n3 + n + 5 comparisons --> O(n3)
3log2n + 2n + 3 comparisons --> O(n)
Comparing Runtime Functions
n log2n n2 2n
1 0 1 2
128 7 16384 1038
256 8 65536 Infinity
65536 16 109 Infinity
16 Meg 24 1014 Infinity
4096 Meg 32 1019 Infinity
Fastest to Slowest
O (1) --> O (log2n) --> O (n) --> O (n2) --> O (n3) -->
O (n4) --> O (2n) --> O (3n)
Analyze the complexity
Program 1: O (n2)
int sum = 0;
int num = 35;
for (int i=1; i<=2*n; i++) {
for (int j=1; j<=n; j++) {
num += j*3;
sum += num;
}
}
for (int k=1; k<=n; k++) {
sum++;
}
Program 2: O (n3)
int sum = 0;
int num = 35;
for (int i=1; i<=2*n; i++) {
for (int j=1; j<=n; j++) {
num += j*3;
sum += num;
}
}
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
for (int k=1; k<=n; k++)
num += j*3;
Program 3: O (n x m)
int sum = 0;
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
sum++;
}
}
Program 4: O (n2)
int sum = 0;
for (int k=1; k<=n; k++) {
sum++;
}
for (int i=1; i<=n; i++) {
for (int j=i; j<=n; j++) {
sum++;
}
}
Program 5: O (n)
int sum = 0;
for (int i=0; i<n; i++) {
if (i > n/2)
sum += 2;
else
sum++;
}
Program 6: O (n2)
int sum = 0;
for (int j=1; j<n; j++) {
sum++;
}
for (int k=0; k<n; k++) {
for (int i=0; i<n; i++) {
sum++;
}
for (int p=0; p<n; p++) {
sum++;
}
for (int m=0; m<n; m++) {
sum++;
}
}
Analyze the complexity
1. Find the maximum in an unsorted list of n numbers.
O (n)
2. Find both the maximum and minimum in an unsorted list.
O (n)
3. Sort n numbers.
O (n x log2n)
4. Multiply two n x n matrices
O (n3)
5. Linear Search (sorted/unsorted)
O (n) - sorted
O (n) - unsorted
6. Binary Search (sorted/unsorted)
O (log2n) - sorted
Algo does not work - unsorted
tart with the first name, and continue looking until x is found.
Then print corresponding phone number.
Assume that we have an array, book, that stores references to objects
containing the name and phone number of each person in the phone book.
Assume there are n names in the phone book (n = book.length).
int whereFound = -1; // position where name found
// Go through each entry, comparing name to x
for (int i=0; i<n; i++) {
// compare next name
if (book[i].getName().equals(x)) {
whereFound = i;
break;
}
}
if (whereFound != -1)
System.out.println (\"Number is \" + book[whereFound].getNumber();
else
System.out.println (\"Name not in phone book.\");
How much time does this take? We look at the number of comparisons.
Best case: 1 step
Average case: n/2 steps
Worse case: n steps
Really these should be multiplied by 2 because each iteration
must compare the loop condition i<n.
Will this work if the list is unsorted?
Linear Search (on a Vector)
Here\'s a variation of the previous linear search algorithm. Assume
that we are searching a sorted Vector of Strings to see if a particular
String is in that Vector.
import java.util.*;
public class LinSearch {
public static void main (String[] args) {
Vector list = new Vector();
list.addElement (\"bear\");
list.addElement (\"dog\");
list.addElement (\"fox\");
int position = search (\"apple\", list);
System.out.println (position);
list.insertElementAt (\"apple\", position);
position = search (\"elk\", list);
System.out.println (position);
list.insertElementAt (\"elk\", position);
position = search (\"giant\", list);
System.out.println (position);
list.insertElementAt (\"giant\", position);
}
public static int search (String s, Vector list) {
int i = 0;
// Inv: list[0..i-1] < s.
// In English: everything we\'ve searched for so
// far is less than s
while (i != list.size() && ((String)list.elementAt(i)).compareTo(s) < 0){
i++;
}
return i;
}
}
