Searching Good

Programming
Searching
Arrays
COMP102 Prog. Fundamentals: Searching Arrays/ Slide 2
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.
Copyright © 2000 by Brooks/Cole Publishing Company

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;

// 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;
}

#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;
}
Ordered Linear Search

 Search an ordered 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]
1 2 3 5 7 10 14 17
 Linear search can stop immediately when it has

passed the possible position of the search value.

 Algorithm:
Start with the first array element (index 0)

while(more elements in the array){
if value at current index is greater than
value, value not found, return –1;
if value found at current index, return index;
Try next element (increment index);
}
value not found, return –1;

// Searches an ordered array of integers
int lsearch(int data[],// input: array
int size, // input: array size
int value // input: value to find
) { // output: index if found
for(int index=0; index<size; index++){
if(data[index] > value)
return -1;
else if(data[index] == value)
return index;
}
return -1;
}

#include <iostream>
using namespace std;
int main() {
const int array_size = 8;
int list[array_size]={1,2,3,5,7,10,14,17};
int search_value;
cout << "Enter search value: ";

cin >> search_value;
cout << lsearch(list,array_size,search_value)
<< endl;
return 0;
}
Binary Search
 Search an ordered 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]
1 2 3 5 7 10 14 17
 Binary search skips over parts of the array if the search

value cannot possibly be there.
6
Copyright © 2000 by Brooks/Cole Publishing Company
Binary Search
 Binary search is based on the “divide-and-
conquer” strategy which works as follows:
 Start by looking at the middle element of the
array
– 1. If the value it holds is lower than the search
element, eliminate the first half of the array from
further consideration.
– 2. If the value it holds is higher than the search
element, eliminate the second half of the array from
further consideration.
 Repeat this process until the element is found,
or until the entire array has been eliminated.
Binary Search
 Algorithm:
Set first and last boundary of array to be searched
Repeat the following:
Find middle element between first and last boundaries;
if (middle element contains the search value)
return middle_element position;
else if (first >= last )
return –1;
else if (value < the value of middle_element)
set last to middle_element position – 1;
else
set first to middle_element position + 1;
Binary Search
// Searches an ordered array of integers
int bsearch(int data[], // input: array
int size, // input: array size
int value // input: value to find
) // output: if found,return index
{ // otherwise, return -1
int first, middle, last;
first = 0;
last = size - 1;
while (true) {
middle = (first + last) / 2;
if (data[middle] == value)
return middle;
else if (first >= last)
return -1;
else if (value < data[middle])
last = middle - 1;
else
first = middle + 1;
}
}
Binary Search
int main() {
const int array_size = 8;
int list[array_size]={1,2,3,5,7,10,14,17};
int search_value;
cout << "Enter search value: ";

cin >> search_value;
cout << bsearch(list,array_size,search_value)
<< endl;
return 0;
}
Example: binary search

A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7]
 14 ? 1 2 3 5 7 10 14 17
first mid last
A[4] A[5] A[6] A[7]
7 10 14 17
first mid last
A[6] A[7]
In this case,
(data[middle] == value) 14 17
return middle;
f mid last

A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7]
 8? 1 2 3 5 7 10 14 17
first mid last
A[4] A[5] A[6] A[7]
7 10 14 17
first mid last
In this case, A[4]

(first == last)
return -1; 7
fml

 4? A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7]
1 2 3 5 7 10 14 17
first mid last
A[0] A[1] A[2]
1 2 3
first mid last
A[2]
In this case,
(first == last)
return -1; 3
fml

Searching Good

Uploaded by

Copyright:

Available Formats

Searching Good

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Searching Good

Uploaded by

Copyright:

Available Formats

Programming

Copyright © 2000 by Broks/Cole Publishing Company

Copyright © 2000 by Brooks/Cole Publishing Company

Unordered Linear Search

Unordered Linear Search

Unordered Linear Search

Ordered Linear Search

 Linear search can stop immediately when it has

Ordered Linear Search

Start with the first array element (index 0)

Ordered Linear Search

Ordered Linear Search

cout << "Enter search value: ";

A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7]

 Binary search skips over parts of the array if the search

cout << "Enter search value: ";

Example: binary search

Example: binary search

In this case, A[4]

Example: binary search

You might also like