• # Searching

Searching is the process of finding the location of a given element in a set of elements. The search is said to be successful if the given element is found i.e., the element does exist in the collection (such as an array); otherwise it is unsuccessful.

Two simple approaches to searching are:

• Linear search: This method traverses a list sequentially to locate the search key.
• Binary search: This method works on sorted lists by progressively making better guesses to find the location of a search key.

## Linear Search

This method traverses a list sequentially to locate the search key.

The algorithm that one chooses generally depends on the organization of the array elements. If the elements are in random order, then one should choose the linear search technique.

## Algorithm

linearsearch (a,n,item,loc)

Here "a" is an array of the size n. This algorithm finds the location of the element "item" in the array "a". If search item is found, it sets loc to the index of the element; otherwise, it sets loc to -1

Begin for i=0 to (n-1) by 1 do if (a[i] = item) then set loc=I exit endif endfor set loc -1 end

## C/C++ Implementation of the Algorithm

.cf { font-family: Lucida Console; font-size: 9pt; color: black; background: white; } .cl { margin: 0px; } .cb1 { color: green; } .cb2 { color: blue; } .cb3 { color: maroon; }

`int linearsearch (int a[], int n, int key)`
`{`
` int i;`
` for(i=0;i<n;i++)`

` {`
` if(a[i]==key)`
` return i;`
` }`
` return -1;`
`}`

## Analysis of Linear Search

In the best possible case, the item may be found at the first position. In that case, the search operation terminates in success with just one comparison.

The worst case occurs when the item is present at the last position or it is missing from the array. In the former case, the search terminates in success with n comparisons. In the latter case, the search terminates in failure with n comparisons. Thus, we find that in the worst case, linear search carries out n operations.

## Complete Program

`/**`
` * Program that illustrates the working of Linear Search`
` * http://www.tech-faq.com`
` */`
` `
`#include <stdio.h>`
` `
`/**`
` * Parameters:`
` * a: array to search in`
` * n: number of elements in the array`
` * key: search key`
` *`
` * Return Value: index of the first occurence`
` * of key in a[], or -1 if not found`
` */`
`int linearsearch (int a[], int n, int key)`
`{`
` int i;`
` for(i=0;i<n;i++)`
` {`
` if(a[i]==key)`
` return i;`
` }`
` return -1;`
`}`
` `
` `
`int main()`
`{`
` int array[50], num, index, element, key;`
` `
` /*Fill the array*/`
` puts("How many elements do you want to create the array with? (Max 50)");`
` scanf("%d", &num);`
` `
` printf("Enter the elements: ");`
` fflush(stdout);`
` `
` for (index=0; index<num; index++) `
` scanf("%d", &array[index]);`
` `
` printf("Enter the search key: ");`
` fflush(stdout);`
` scanf("%d", &key);`
` `
` if ( (index=linearsearch(array, num, key)) != -1)`
` printf("The element was found at index: %dn", index);`
` else`
` printf("Could not find %dn", key);`
` `
` return 0;`
`}`

## Binary Search

This method works on sorted lists by progressively making better guesses to find the location of a search key.

## Illustration

Consider the following array:

 3 10 15 20 35 40 60

Suppose we want to search the element "15"

1. We take beg = 0, end = 6 and compute the location of the middle element as
2. We then compare the search key with mid i.e. a[mid]=a[3] is not equal to 15. Since beg<end, we start the next iteration.
3. As a[mid]=20>15, therefore, we take end = mid-1 = 3-1 = 2 whereas beg remains the same.. Thus
4. Since a[mid] i.e. a[1]=10<15, therefore, we take beg=mid+1=1+1=2, while end remains the same.
5. Now beg=end. Compute the mid element:

Since a[mid] i.e. a[2]=15, the search terminates on success.

## Algorithm

Binarysearch(a,n,item,loc)

Begin
set beg=0
set end=n-1
set mid=(beg+end)/2
while((beg<=end) and(a[mid]!=item) do
if(item<a[mid]) then
set end=mid-1
else
set beg=mid+1
endif
set mid=(beg+end)/2
endwhile
if(beg>end) then
set loc=-1
else
set loc=mid
endif
end

## C/C++ Implementation

.cf { font-family: Lucida Console; font-size: 9pt; color: black; background: white; } .cl { margin: 0px; } .cb1 { color: green; } .cb2 { color: blue; } .cb3 { color: maroon; }

`int binarysearch(int a[], int n, int key)`
`{`
`    int beg,end,mid;`
`    beg=0; end=n-1;`
`    mid=(beg+end)/2;`
`    while((beg<=end)&&(a[mid]!=key))`
`    {`
`        if(key<a[mid])`
`            end=mid-1;`
`        else`
`            beg=mid+1;`
`        mid=(beg+end)/2;`
`    }`
`    if(beg>end)`
`        return -1;`
`    else`
`        return mid;`
`}`

## Analysis of Binary Search

In each iteration, the search is reduced to one-half of the array. For n elements in the array, there will be a maximum of log2 n iterations.

Thus, the complexity of binary search is O(log2 n).

## Complete Program Listing

`/**`
` * Program that illustrates the working of Binary Search`
` * http://www.tech-faq.com`
` */`
` `
`#include <stdio.h>`
` `
`int binarysearch(int a[], int n, int key)`
`{`
`    int beg,end,mid;`
`    beg=0; end=n-1;`
`    mid=(beg+end)/2;`
`    while((beg<=end)&&(a[mid]!=key))`
`    {`
`        if(key<a[mid])`
`            end=mid-1;`
`        else`
`            beg=mid+1;`
`        mid=(beg+end)/2;`
`    }`
`    if(beg>end)`
`        return -1;`
`    else`
`        return mid;`
`}`
` `
`int main()`
`{`
`    int arr[50], n, key, index;`
` `
`    printf("How many elements do you want to create the array with?(max 50): ");`
`    fflush(stdout);`
` `
`    scanf("%d", &n);`
` `
`    puts("Enter the array elements in ascending order");`
`    for (index = 0; index < n; index++)`
`        scanf("%d", &arr[index]);`
` `
`    printf("Enter the search key: ");`
`    fflush(stdout);`
` `
`    scanf("%d", &key);`
` `
`    index = binarysearch(arr, n, key);`
` `
`    if (index == -1)`
`        puts("Sorry, the given key was not found");`
`    else`
`        printf("The given key was found at index:%dn", index);`
` `
`    return 0;`
`}`

} 239 queries in 0.338 seconds.