Transcript Search - Temple University

Search - CIS 1068
Program Design and Abstraction
Zhen Jiang
CIS Dept.
Temple University
1050 Wachman Hall, Main Campus
Email: [email protected]
4/8/2015
1
Table of Contents








Introduction to searching problem
Problem statement
Linear search algorithm
Binary search
Binary search algorithm
How much fast is binary search?
Search mechanics in java
Summary
4/8/2015
2
The Search Problem
Considering
a sequence of characters that are contained in a string
e.g., String str= “hello”;
and a particular character in another string,
e.g., String str2 = “l”;
Find 1st appearance of such a character in the
original group
e.g., return str.indexOf(str2)
4/8/2015
3
Problem Statement
Given
a set of data
e.g., int [] arr = {10, 2, 7, 9, 7, 4};
and a particular value,
e.g., int val = 7;
Find the first index/position of the value in the
data.
e.g., return index = 2
4/8/2015
4
Problem Statement, revisited:
Input:
A set of data (an array, ArrayList, LinkedList, …)
A single data element
Output:
Position of the data element in the data set, or
-1 if the element does not appear in the data set
4/8/2015
5
For instance


Price is right (click on this link to try)
To see if you can get the price quickly…
4/8/2015
6
Linear Search Algorithm
(p541)
#
#
#
#
Input: Array D, integer key
Output: first index of key in D,
or -1 if not found
also called sequential search
For i = 0 to last index of D:
if D[i] equals key:
return i
return -1
4/8/2015
7
# Input: Array D of Business objects,
#
phone number key
# Output: first index where key’s phone
# number matches D, or -1 if not found
Business:
For i:= 0 to end of D:
phone #
if D[i].phone matches key:
address
return i
name
return -1
4/8/2015
8
1.
2.
3.
Implement a class called Business that includes
fields for name, address, and phone number, plus a
constructor and accessor methods.
Create a class called YellowPages that stores a set
of Business objects in an array.
Write a LinearSearch method for the YellowPages
class that finds the index of a Business, given its
phone number.
4/8/2015
9
Binary Search

Imagine finding the price among the range up to
$100,000,000


Linear search would take a long time
Random guess is even worse!
4/8/2015
10

Two common search techniques are:

Indexing (used on the Web and in databases)

Imagine flipping through the Yellow Pages, looking for a
pizza place near you.



It’s pretty easy – you just flip to the section for ‘P’, then look for ‘Pi’,
then ‘Piz’, …, ‘Pizza’.
We can learn about indexing in later CIS classes
Binary search

4/8/2015
We’ll discuss binary search because it’s simpler
11

Now imagine doing the reverse: find the name of a
business given just their phone number.


4/8/2015
What algorithm will find the number in the phone book?
Answer: you need to use (some version of) linear search!
Ugh.
12

Normally, when you search the phone book,
you implicitly use the fact that it’s sorted:
The smallest element (alphabetically first element)
appears first.
Then the next smallest,
…
Then the biggest (alphabetically last) element.

Binary search does the same thing, and it
only works if your data (array) is sorted.
4/8/2015
13
Step 1: Define left and right boundaries for searching
Step 2: Define middle of the search region
Repeat!
Step 3: Compare the middle with our key
Find key:
29
Comparison:
D[mid] < key
Comparison:
-15
-7
left
4/8/2015
-6
-2
0
8
mid
left
10
D[mid] = key!
29
mid
31
40
right
14
Binary Search Algorithm
# Input: Sorted Array D, integer key
# Output: first index of key in D, or -1 if not found
left = 0, right = index of last element
while left <= right:
middle = index halfway between left, right
if D[middle] matches key:
return middle
else if key comes before D[middle]:
// b/c D is sorted
right = middle -1
else:
left = middle + 1
return -1
4/8/2015
15
public static int bs(int [ ] n, int first, int last, int v){
int middle;
if (first > last) return -1;
middle = (first + last)/2;
if(n[middle] = = v) return middle;
else if ( n[middle] < v) return bs(n, middle+1, last, v);
else return bs(n, first, middle-1, v);
}
4/8/2015
16
Find out what will be the print out results of the following program
and trace the position (subscript value) of each access of the
array n (i.e., the value of variable middle).
public class ArrayRecursive {
public static void main(String [ ] args){
int [ ] n = {101, 142, 147, 189, 199, 207, 222, 234, 289, 296, 310,
319, 388, 394, 417, 429, 447, 521, 536, 600};
System.out.println( “bs(”+102+“)=”+bs(n, 0, n.length-1, 102));
System.out.println( “bs(”+296+“)=”+bs(n, 0, n.length-1, 296));
System.out.println( “bs(”+289+“)=”+bs(n, 0, n.length-1, 289));
}
}
4/8/2015
17

Implement a binary search method in
your Business class
4/8/2015
18
How much faster is binary
search?

Way, way faster

Assuming the array is already sorted
For an array of size:
Linear search might
visit:
Binary search might
visit:

24 = 16
But precisely
how much? 4+1
16 elements
28 = 256
256 elements
8+1 = log2(256)+1
212 = 4096
4096 elements
12+1 = log2(4096)+1
2n = m elements
m elements
n + 1 = log2(m) + 1
4/8/2015
= log2(16)+1
19
Big O notation

Analyzing algorithms/processes for
efficiency




Fast?
T(n) = O(n2) tells the order of n2 time complexity.
n∞
T(n) = O(g(n))


4/8/2015
c1g(n) ≤ T(n) ≤ c2g(n)
Linear search T(n) and binary search T(log n)
20
Little O notation


T(n) = o(n2) tells that T grows much
slower than n2.
T(n) = o(g(n))
T(n)
lim
=0
n->¥ g(n)
4/8/2015
21

Code:
n=keyboard.nextInt(); // try 5!
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 10; j++) {
System.out.print((i * j) + " ");
}
System.out.println();
}
Output:
1
2
3
4
5
2 3 4 5 6 7 8 9 10
4 6 8 10 12 14 16 18 20
6 9 12 15 18 21 24 27 30
8 12 16 20 24 28 32 36 40
10 15 20 25 30 35 40 45 50
4/8/2015
22

Code:
n=keyboard.nextInt(); // try 6!
for (i = 1; i<=n; i++) System.out.print(“*”);
System.out.println(“”);
for (i = 1; i <= n-2; i++) {
System.out.print(“*”);
for (int j = 1; j <= n-2; j++)
System.out.print(“ ”);
System.out.println(“*”);
}
for (i = 1; i<=n; i++) System.out.print(“*”);
System.out.println(“”);
Output:
******
*
*
*
*
*
*
*
*
******
4/8/2015
23

Code:
n=keyboard.nextInt(); // try 6!
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
System.out.print("*");
}
System.out.println();
}
Output:
*
**
***
****
*****
******
4/8/2015
24
Java Mechanics in Java
The Java class Arrays has numerous helpful methods
built in, including a binary search method:
public static int binarySearch(int[] a, int key):
Searches the specified array of ints for the specified
value using the binary search algorithm.
Example:
int index = Arrays.binarySearch(arr, 29);
4/8/2015
25
Summary





The requirement for it to work (array is pre-sorted)
How to simulate it on an example array

That is, what sequence of indexes are compared with the
key for a specific input key?
Write the binary search algorithm for it
Advantages and disadvantages compared with linear search
(also called sequential search)
How to use Arrays.binarySearch ( )
4/8/2015
26