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;

}

I have read all your articles. I wonder why you can write them. They are easy to understand and accessible. They help me much too. I'm thankful if you can upload more posts later. Thanks for your sharing.

ReplyDeleteHướng dẫn đăng ký B30 VinaPhone, Đăng ký Mimax sinh viên VinaPhone, Đăng ký Mimax50 VinaPhone, Đăng ký 3G VinaPhone 1 ngày chỉ 5K,7K,10K

I'm trying to learn more knowledge and your articles are so useful for me. I can understand them easily. They aren't science rocket. I even can apply them in ordinary life. I'm grateful for your sharing. I hope you will write often and post more articles. email-with-love free online2018,apps email-with-love, http://dichvuvina.vn

ReplyDeleteHold writing.Thank you for your article post.Really getting excited about read more. Really Cool.I enjoy and recognize your post.Thanks Again.

ReplyDeletesale pop online

sales pop master app

Hold writing.Thank you for your article post.Really getting excited about read more. Really Cool.I enjoy and recognize your post.Thanks Again.

ReplyDeleteDiscount master app

Discount master app

For space outside the milk tea shop closer to nature, outdoor space should use speakers with greater capacity, products such as garden speakers, imitation stone speakers, are products with designs The most natural to create interesting feeling when enjoying. Because it must work in the weather conditions heat so the shell is made very firmly with high durability, the quality of the speaker is imported genuine. Good sound, making good clear sound even when used in wide space

ReplyDeleteGái gọi Mỹ Đình - Đình Thôn, gái gọi Nguyễn Khánh Toàn, gái gọi hà nội, gái gọi Phố Cổ - Quán Sứ

I have read all your articles. I wonder why you can write them. They are easy to understand and accessible. They help me much too. I'm thankful if you can upload more posts later. Thanks for your sharing.

ReplyDeleteapp autoketing

https://apps.shopify.com/shipping-bar-master

https://bit.ly/2BXG37u