Programming

Searching
Arrays
 Searching
• When we maintain a collection of data, one of the
operations we need is a search routine to locate desired
data quickly.
• Here’s the problem statement:

Given a value X, return the index of X in the array, if such X exists. Otherwise,
return NOT_FOUND (-1). We assume there are no duplicate entries in the
array.
• We will count the number of comparisons the algorithms
make to analyze their performance.
– The ideal searching algorithm will make the least possible number
of comparisons to locate the desired data.
– Two separate performance analyses are normally done, one for
successful search and another for unsuccessful search.

©The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Chapter 11 - 2
COMP102 Prog. Fundamentals: Searching Arrays/ Slide 3

Searching
 The process used to find the location of a target
among a list of objects
 Searching an array finds the index of first
element in an array containing that value

Copyright © 2000 by Broks/Cole Publishing Company

A division of International Thomson Publishing Inc.
COMP102 Prog. Fundamentals: Searching Arrays/ Slide 4

Copyright © 2000 by Brooks/Cole Publishing Company

A division of International Thomson Publishing Inc.
COMP102 Prog. Fundamentals: Searching Arrays/ Slide 5
COMP102 Prog. Fundamentals: Searching Arrays/ Slide 6

Unordered Linear Search

 Search an unordered array of integers for a value
and return its index if the value is found. Otherwise,
return -1.
A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7]

14 2 10 5 1 3 17 2
 Algorithm:
Start with the first array element (index 0)
while(more elements in array){
if value found at current index, return index;
Try next element (increment index);
}
Value not found, return -1;
COMP102 Prog. Fundamentals: Searching Arrays/ Slide 7

Unordered Linear Search

// Searches an unordered array of integers
int search(int data[], //input: array
int size, //input: array size
int value){ //input: search value
// output: if found, return index;
// otherwise, return –1.
for(int index = 0; index < size; index++){
if(data[index] == value)
return index;
}
return -1;
}
COMP102 Prog. Fundamentals: Searching Arrays/ Slide 8

Unordered Linear Search

#include <stdio.h>
#include <conio.h>
int main() {
int list[]={14,2,10,5,1,3,17,2};
int search_value,index;
printf(“ Enter search value: “);
scanf(“%d”, &search_value);
index=search(list,array_size,search_value)
if(index!0)
printf(“Search Value=%d found in index=
%d”,search_value,index);
return 0;
}
 How Long Does Linear Search Take?
Okay, great, now we know how to search.
But how long will our search take?
That’s really three separate questions:
 How long will it take in the best case?

 How long will it take in the worst case?

 How long will it take in the average case?

Search Lesson
CS1313 Spring 2009 9
 Linear Search: Best Case
How long will our search take?
In the best case, the target value is in the first element of the
array.
So the search takes some tiny, and constant, amount of time.
Computer scientists denote this O(1) – which will be
explained later.
In real life, we don’t care about the best case, because it so
rarely actually happens.

Search Lesson
CS1313 Spring 2009 10
 Linear Search: Worst Case
How long will our search take?
In the worst case, the target value is in the last element of the
array.
So the search takes an amount of time proportional to the
length of the array.
Computer scientists denote this O(n) – which will be
explained later.

Search Lesson
CS1313 Spring 2009 11
 Linear Search: Average Case
How long will our search take?
In the average case, the target value is somewhere in the
array.
In fact, since the target value can be anywhere in the array,
any element of the array is equally likely.
So on average, the target value will be in the middle of the
array.
So the search takes an amount of time proportional to half the
length of the array – also proportional to the length of the
array – O(n) again!

Search Lesson
CS1313 Spring 2009 12
 Why Do We Care About Search Time?
We know that time is money.
So finding the fastest way to search (or any task) is good,
because then we’ll save time, which saves money.

Search Lesson
CS1313 Spring 2009 13
 “Big-O” Notation #1
Suppose we can describe the amount of time it takes to do a
task in terms of the number of pieces of data in the task.
For example, suppose that our search algorithm takes 3n + 12
time units to execute.
Well, as n becomes very big – a million, a billion, etc – then
we stop caring about the 12, because it’s basically zero
compared to the 3n term.

Search Lesson
CS1313 Spring 2009 14
 “Big-O” Notation #2
Suppose we can describe the amount of time it takes to do a
task in terms of the number of pieces of data in the task.
For example, suppose that our search algorithm takes 3n + 12
time units to execute.
No matter the size of n, the 3 in 3n isn’t all that interesting,
because running on a different computer changes the actual
time cost of a “time unit.”

Search Lesson
CS1313 Spring 2009 15
 “Big-O” Notation #4
Suppose we can describe the amount of time it takes to do a
task in terms of the number of pieces of data in the task.
For example, suppose that our search algorithm takes 3n + 12
time units to execute.
So, we really only care about the n in 3n + 12.

Search Lesson
CS1313 Spring 2009 16
 “Big-O” Notation #5
Now, suppose we have an algorithm that, for n pieces of data,
takes 0.03n2 + 12n + 937.88 time units.
Again, we don’t care about the constants.
And, as n becomes big – a million, a billion, etc – we no
longer care about the n term (12n), because it grows much
slower than the n2 term. Nor do we care about the constant
term (937.88), which doesn’t grow at all.
That is, as n becomes big, the smaller terms are so tiny as to
be pretty much zero.

Search Lesson
CS1313 Spring 2009 17
 “Big-O” Notation #6
In the general case, suppose an algorithm on n pieces of data
takes:
cknk + ck-1nk-1 + ck-2nk-2 + ... + c1n + c0
for constants c0, c1, etc.
Keep in mind the principles that we’ve already seen:
 We don’t care about the constants c .
i
 We don’t care about the terms smaller than nk.

We really only care about nk.

So we say that this algorithm has time complexity
“of order nk.”
We denote this O(nk).
We pronounce it “big-O of n to the k.”
Search Lesson
CS1313 Spring 2009 18
 A Better Search?
Consider how you search for someone in the phone book –
say, Henry Neeman.
You start with the first letter of their last name, N.
You guess roughly where N would be in the phonebook.
You open to that page.
If you’re wrong, you move either forward or backward in the
book – that is, if you actually opened to J, you move
forward, but if you opened to T, you move backward.
You keep repeating this action until you find Neeman.

Search Lesson
CS1313 Spring 2009 19
 Faster Search Requires Sorted Data
Why not use linear search?
Linear search means start at the beginning, and look at every
piece of data until you find your target.
This is much much slower than the way you search a
phonebook in real life.
Why?
The reason you can do the phonebook search so quickly is
because the names in the phonebook are sorted –
specifically, they’re in alphabetical order by last name, then
by first name.

Search Lesson
CS1313 Spring 2009 20
 Binary Search
The general term for a smart search through sorted data is a
binary search.
1. The initial search region is the whole array.
2. Look at the data value in the middle of the search region.
3. If you’ve found your target, stop.
4. If your target is less than the middle data value, the new
search region is the lower half of the data.
5. If your target is greater than the middle data value, the
new search region is the higher half of the data.
6. Continue from Step 2.

Search Lesson
CS1313 Spring 2009 21
 Binary Search Code
int binary_search (float* array, int number_of_elements,
float target_value)
{ /* binary_search */
const int nonexistent_element = -1;
const int first_element = 0;
int low_element, middle_element, high_element;
/* Idiotproofing goes here. */
/* Start with the entire array as the search region. */
low_element = first_element;
high_element = number_of_elements – 1;

Search Lesson
CS1313 Spring 2009 22
 Binary Search Code
while ((low_element > first_element) &&
(high_element < number_of_elements) &&
(low_element < high_element)) {
/* Examine the middle of the current search region. */
middle_element = (low_element + high_element) / 2;
/* What should we search next? */
if (array[middle_element] < target_value) {
/* Reduce the search region to the lower half. */
high_element = middle_element - 1;
} /* if (array[middle_element] < target_value) */
else if (array[middle_element] > target_value) {
/* Reduce the search region to the higher half. */
low_element = middle_element + 1;
} /* if (array[middle_element] > target_value) */
else {
/* Target has been found, so stop searching. */
low_element = middle_element;
high_element = middle_element;
} /* if (array[middle_element] > ...)...else */
} /* while (low_element < high_element) */
if (high_element == low_element) {
return middle_element;
} /* if (high_element == low_element) */
return nonexistent_element;
} /* binary_search */

Search Lesson
CS1313 Spring 2009 23
 Binary Search Example #1

-86 -37 -23 0 5 18 21 64 97

low middle high

Searching for 18.

Search Lesson
CS1313 Spring 2009 24
 Binary Search Example #2

-86 -37 -23 0 5 18 21 64 97

low high
middle

Searching for 18.

Search Lesson
CS1313 Spring 2009 25
 Binary Search Example #3

-86 -37 -23 0 5 18 21 64 97

low high
middle

Searching for 18: found!

Search Lesson
CS1313 Spring 2009 26
 Time Complexity of Binary Search #1
How fast is binary search?
Think about how it operates: after you examine a value, you
cut the search region in half.
So, the first iteration of the loop, your search region is the
whole array.
The second iteration, it’s half the array.
The third iteration, it’s a quarter of the array.
...
The kth iteration, it’s (1/2k-1) of the array.

Search Lesson
CS1313 Spring 2009 27
 Time Complexity of Binary Search #2
How fast is binary search?
For the kth iteration of the binary search loop, the search
region is (1/2k-1) of the array.
What’s the maximum number of loop iterations?
log2n
That is, we can’t cut the search region in half more than that
many times.
So, the time complexity of binary search is O(log2n).

Search Lesson
CS1313 Spring 2009 28
 Time Complexity of Binary Search #3
How fast is binary search?
We said that the time complexity of binary search is O(log2n).
But, O(log2n) is exactly the same as O(log n).
Why?
Well, we know from math class that
logax  logbx / logba
So the relationship between logs to various bases is simply a
constant, (1 / logba).
Therefore, O(log n) is the same as O(logbn) for any base b –
we don’t care about the base.

Search Lesson
CS1313 Spring 2009 29
 Need to Sort Array
Binary search only works if the array is already sorted.
It turns out that sorting is a huge issue in computing – and the
subject of our next lecture.

Search Lesson
CS1313 Spring 2009 30