Searching is one of the most
common problems that arise in computing. Searching is the algorithmic process
of finding a particular item in a collection of items. A search typically answers
either True or False as to whether the item is present. On
occasion it may be modified to return where the item is found. Search
operations are usually carried out on a key field.

Consider searching for a given value k in
an array A of size n. There are 2 basic approaches: sequential search and binary
search.

**Linear (Sequential) Search**

When data items are stored in a
collection such as a list or array , we say that they have a linear or
sequential relationship. Each data item is stored in a position relative to the
others. In C array, these relative
positions are the index values of the individual items. Since these index
values are ordered, it is possible for us to visit them in sequence. This
process gives rise to our first searching technique, the sequential search.

Starting at the first item in the
list, we simply move from item to item, following the underlying sequential
ordering until we either find what we are looking for or run out of items. If
we run out of items, we have discovered that the item we were searching for was
not present.

The following function will
return the position of an element k in an array A of size n.If the element is
not present the function will return -1.

int sequentialsearch(int A[],int n ,int k)

{ int i;

for (i = 0; i < n; i++) {

if (A[i]==k) return i;

}

return -1;

}

If the values are in sorted order,
then the algorithm can sometimes quit and return false(-1) without having to look at all of the values in
the array. If k is not in the array and if the current value is greater than
k then we can return -1. Here's the code for this version:

int sortedsequentialsearch(int A[], int n,int k)

{ int i;

//
precondition: A is sorted (in ascending order)

for (i = 0;i < n; i++) {

if (A[i]==k) return i;

if (A[i]>k) return -1;

}

return -1;

}

The
worst-case time for a sequential search is always O(N).

**Binary Search**

When the values are in sorted order, a better approach than the one given above is to use binary search. The algorithm for binary search starts by looking at the middle item x. If x is equal to k, it quits and returns true(position). Otherwise, it uses the relative ordering of x and k to eliminate half of the array (if k is less than x, then it can't be stored to the right of x in the array; similarly, if it is greater than x, it can't be stored to the left of x). Once half of the array has been eliminated, the algorithm starts again by looking at the middle item in the remaining half. It quits when it finds k or when the entire array has been eliminated.

Here's the code for binary search:

int binarysearch(int
A[],int low,int high,int k)

{

// precondition: A is sorted (in ascending order)

if (low >
high) return -1;

int middle =
(low + high) / 2;

if (A[middle]==key) return middle;

if (k<A[middle])
{

//
recursively search the left part of the array

return(binarysearch(A, low,
middle-1, k));

}

else {

//
recursively search the right part of the array

return
binarysearch(A, middle+1, high, k);

}

}

The worst-case time for binary search is proportional
to log2 N: the number of times N can be divided in half before there is
nothing left. Using big-O notation, this is O(log N).

The binary search technique can also be implemented using non recursive iterative way

**C program to implement iterative Binary Search**

#include <stdio.h>

// A iterative binary search function. It returns

// location of k in given array A[l..r] if present,

// otherwise -1

int binarysearch(int A[], int l, int r, int k)

{int m;

while (l <= r)

{

m = l + (r-1)/2;

// Check if k is present at mid

if (A[m] == k)

return m;

// If k greater, ignore left half

if (A[m] < k)

l = m + 1;

// If k is smaller, ignore right half

else

r = m - 1;

}

// if we reach here, then element was

// not present

return -1;

}

int main(void)

{

int A[30];

int
k,n,I,result

printf(“Enter
the number of elements\n”);

scanf(“%d”,&n);

printf(“Enter
the of elements in sorted order\n”);

for(i=0;i<n;i++)

scanf(“%d”,&A[i]);

printf(“Enter
the key element to serach…\n”);

scanf(“%d”,&k);

result
= binarysearch(A, 0, n-1, k);

(result == -1)? printf("Element is not present in array"): printf("Element is present at "

"index %d", result);

return 0;

}

(result == -1)? printf("Element is not present in array"): printf("Element is present at "

"index %d", result);

return 0;

}

## Comments

## Post a Comment