Defn
In computer science, linear search or
sequential search is a method for finding a
particular value in a list, that consists of
checking every one of its elements, one at a
time and in sequence, until the desired one is
found. Wikipedia
Code
for(i=0;i<l;i++)
{
if(arr[i]==k)
{
pos=i+1;
break;
}
}
if(pos!=0)
printf(“%d is found in the list, at position %d\
n”,k,pos);
else
printf(“%d is not in the list\n”,k);
}
Algorithm
Get the input numbers from the user and store it in
the array
Get the input from the user for the number(‘k’) that
has to be searched
Initialize a for loop and run it till it reaches the nth
element in the array
Compare the value of ‘k’ with the array element as per
the loop index
If the value of ‘k’ is matched with array value then set
the flag as found
After exiting the for loop check the flag variable.
If it is set the print as element found at position
If not print as element is not found
Performance Study
the probability that Key will be the first item is 1/n, that it will be
the second item is also 1/n and so on for each item.
the average number of items to be examined before you find the
item you're looking for is given by:
(1 + 2 + 3 + .... + n)/n
which is n * (n + 1)/2/n
which is (n + 1)/2.
In 'big O' notation, a linear search algorithm is O(n).
A binary search or half-interval search
algorithm finds the position of a specified
input value (the search "key") within an
array sorted by key value
the array should be arranged in ascending or
descending order.
A binary search looks for an item in a list
using a divide-and-conquer strategy
Binary search
low:=0; high:=n-1;
while low<high do
begin
mid:=(low+high) div 2;
if X==a[mid]
then return mid;
else if x>a[mid] then
low:=mid+1;
else
high:=mid-1;
end;
return key not found;
Binary Search
Binary search.Given value and sorted array a[], find index i
such that a[i] = value, or report that no such index exists.
Invariant. Algorithm maintains a[low] value a[high].
Ex. Binary search for 33.
6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
low high
Binary Search
6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
low mid high
Binary Search
6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
low high
Binary Search
6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
low mid high
Binary Search
6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
low high
Binary Search
6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
low mid high
Binary Search
6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
low
high
Binary Search
6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
low
high
mid
Binary Search
6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
low
high
mid
Performance Study
Thank You
