Searching

• Most common application.

• Searching is the process used to find the location of a target among
a list of objects.
• In case of arrays, searching means given a value, we want to find
the location (i.e. index).
• Two searches for array:
– Sequential search (linear)
– Binary search
• Linear search is used to locate an item in any array.
• Binary search requires the list to be sorted.
 Linear Search
• Step through array of elements, one at a time.
• Look for element with matching key.
• Search stops when
– element with matching key is found
– or when search has examined all the elements without
success.
 Algorithm for linear Search
Step 1: start
Step 2: read size of the array as n
Step 3: read n number of array elements as a[]
Step 4: read the search key
Step 5: initialize i<-0, declare p
Step 6: repeat step 7 and 8 until i<n
Step 7: if a[i] is desired search key then
p <- i
Step 8: increment i by 1
Step 9: if search key found then
write search key found at position p
else
write search key not found
Step 10: stop
Example
Target data found
 Program to perform linear search
#include<conio.h>
void main()
{
int arr[10], i, key, n, found=0, pos;
clrscr();
printf("Enter the array size : ");
scanf("%d",&n);
printf("Enter Array Elements : ");
for(i=0; i<n; i++)
scanf("%d",&arr[i]);
printf("Enter the number to be search : ");
scanf("%d",&key);
for(i=0; i<n; i++)
{
if(arr[i]==key)
{
found=1;
pos=i+1;
break;
}
}
if(found==0)
{
printf("Number not found..!!");
}
else
{
printf("%d found at position %d",key, pos);
}
getch();
}
 Linear Search Analysis
• We must determine the O-notation for the number of operations
required in search.
• Number of operations depends on n, the number of entries in the
list.
Worst case:
• For an array of n elements, the worst case time for serial search
requires n array accesses: O(n).
• Consider cases where we must loop over all n elements:
– desired element appears in the last position of the array
– desired element does not appear in the array at all
 Average case for linear search
• Assumptions:
– All keys are equally likely in a search
– We always search for a key that is in the array
Example:
• We have an array of 10 elements.
• If search for the first element, then it requires 1 array access; if the
second, then 2 array accesses. etc.
• The average of all these searches is:
– (1+2+3+4+5+6+7+8+9+10)/10 = 5.5
• Generalize for array size n.
• Expression for average-case running time:
(1+2+…+n)/n = n(n+1)/2n = (n+1)/2
• Therefore, average case time complexity for linear search is O(n)
 Binary Search
• Perhaps we can do better than O(n) in the average case?
• Assume that we are give an array of elements that is sorted.
For instance:
– an array of elements with integer keys sorted from
smallest to largest (e.g., ID numbers), or
– an array of elements with string keys sorted in alphabetical
order (e.g., names).
 Algorithm for binary search
Step 1: start
Step 2: read size of array as n
Step 3: Read array elements as a
Step 4: Read search key
Step 5: initialize high<-n, low<-0
Step 6:
i. if(low < high) then
middle = (low+high)/2 ;
if(key == a[middle])
key has been found!
else if(key < a[middle])
//search for key in area before midpoint
high <- middle-1 and goto step 6 (i)
else
//search for key in area after midpoint
low<-middle+1 and goto step 6 (i)
ii. Else
search key not found
Step 7: stop
 Binary Search

Example: sorted array of integer keys. Target=7.

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

3 6 7 11 32 33 53
Example: sorted array of integer keys. Target=7.

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

3 6 7 11 32 33 53

Find approximate midpoint

Example: sorted array of integer keys. Target=7.

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

3 6 7 11 32 33 53

Is 7 = midpoint key? NO.

 Binary Search

Example: sorted array of integer keys. Target=7.

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

3 6 7 11 32 33 53

Is 7 < midpoint key? YES.

 Binary Search

Example: sorted array of integer keys. Target=7.

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

3 6 7 11 32 33 53

Search for the target in the area before midpoint.

Example: sorted array of integer keys. Target=7.

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

3 6 7 11 32 33 53

Find approximate midpoint

Example: sorted array of integer keys. Target=7.

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

3 6 7 11 32 33 53

Target = key of midpoint? NO.

Example: sorted array of integer keys. Target=7.

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

3 6 7 11 32 33 53

Target < key of midpoint? NO.

Example: sorted array of integer keys. Target=7.

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

3 6 7 11 32 33 53

Target > key of midpoint? YES.

Example: sorted array of integer keys. Target=7.

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

3 6 7 11 32 33 53

Search for the target in the area after midpoint.

Example: sorted array of integer keys. Target=7.

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

3 6 7 11 32 33 53

Find approximate midpoint.

Is target = midpoint key? YES.
 Program to perform binary search
#include<conio.h>
void main()
{
int n, i, arr[50], key, low, high, middle;
clrscr();
printf("Enter total number of elements :");
scanf("%d",&n);
printf("Enter %d number :", n);
for (i=0; i<n; i++)
scanf("%d",&arr[i]);
printf("Enter a number to find :");
scanf("%d", &key);
low = 0;
high = n-1;
middle = (low+high)/2;

while (low <= high)

{
Output
 Binary Search: Analysis
• Worst case complexity
• What is the maximum depth of recursive calls in binary search
as function of n?
• Each level in the recursion, we split the array in half (divide by
two).
• Therefore maximum recursion depth is floor(log2n) and worst
case = O(log2n).
• Average case is also = O(log2n).