Wednesday, 1 March 2017

Binary search

Binary search

Binary search algorithm finds given element in a list of elements with O(log n) time complexity where n is total number of elements in the list. The binary search algorithm can be used with only sorted list of element. That means, binary search can be used only with list of element which are already arranged in a order. The binary search can not be used for list of element which are in random order. This search process starts comparing of the search element with the middle element in the list. If both are matched, then the result is "element found". Otherwise, we check whether the search element is smaller or larger than the middle element in the list. If the search element is smaller, then we repeat the same process for left sublist of the middle element. If the search element is larger, then we repeat the same process for right sublist of the middle element. We repeat this process until we find the search element in the list or until we left with a sublist of only one element. And if that element also doesn't match with the search element, then the result is "Element not found in the list".
Binary search is implemented using following steps...

Step 1: Read the search element from the user
Step 2: Find the middle element in the sorted list
Step 3: Compare, the search element with the middle element in the sorted list.
Step 4: If both are matching, then display "Given element found!!!" and terminate the function
Step 5: If both are not matching, then check whether the search element is smaller or larger than middle element.
Step 6: If the search element is smaller than middle element, then repeat steps 2, 3, 4 and 5 for the left sublist of the middle element.
Step 7: If the search element is larger than middle element, then repeat steps 2, 3, 4 and 5 for the right sublist of the middle element.
Step 8: Repeat the same process until we find the search element in the list or until sublist contains only one element.
Step 9: If that element also doesn't match with the search element, then display "Element not found in the list!!!" and terminate the function.


Binary search is a fast search algorithm with run-time complexity of Ο(log n). This search algorithm works on the principle of divide and conquer. For this algorithm to work properly, the data collection should be in the sorted form.
Binary search looks for a particular item by comparing the middle most item of the collection. If a match occurs, then the index of item is returned. If the middle item is greater than the item, then the item is searched in the sub-array to the left of the middle item. Otherwise, the item is searched for in the sub-array to the right of the middle item. This process continues on the sub-array as well until the size of the subarray reduces to zero.


Algorithm(BSEARCH(A,N,ITEM)
given a one dimensional sorted array A with N elements whose index ranges from 1to N and TARGET represents item to be searched. This algorithm finds and return the location LOC of ITEM in array A or set LOC=-1 if search is unsuccessful. Here LOC,BEG,MID,END are the local variables. The BEG, MID and END variables represents index of the first, middle and last element of the array under consideration respectively.
1.  LOC  ß  -1       [initialize the location counter]
2.  BEGß1,END ßN    [initialize]
3.  Repeat steps 4 and 5 while BEG <= END[search for target]
4.  MID=[(BEG+END)/2
5.      If A[MID] == TARGET [item found]
          LOCßMID
          Exit loop
          Else If] TARGET >A[MID then      [look in the second half]
          BEGß MID+1
          Else      [or look for second half]
          ENDßMID-1
          [end of if structure]
[end of step 3 loop]
6. Return LOC 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include<stdio.h>
#include<conio.h>
int main()
{
    int i, first, last, middle, n, target, array[100];
    printf("Enter number of elementsn"); canf("%d",&n);
    printf("Enter %d integersn", n);
    for (i = 0; i < n; i++)
    scanf("%d",&array[i);
    printf("Enter value to findn");
    scanf("%d", &target);
    first = 0;
    last = n - 1;
    middle = (first+last)/2;
    while (first <= last)
    {
        if (array[middle] < target)
        first = middle + 1;
        else if (array[middle] == target)
        {
            printf("%d found at location %d.n", target, middle+1);
            break;
        }
        else last = middle - 1;
        middle = (first + last)/2;
    }
    if (first > last)
    printf("Not found! %d is not present in the list.n", target);
    return 0;
}
/************************************************/
/*Binary search using function*/
#include <stdio.h>
int BinarySearching(int [], int , int )
int main()
{
    int count, element, limit, arr[50], position;
    printf("Enter the Limit of Elements in Array:t");
    scanf("%d", &limit);
    printf("Enter %d Elements in Array: n", limit);
    for(count = 0; count < limit; count++)
    {
        scanf("%d", &arr[count]);
    }
    printf("Enter Element To Search:t");
    scanf("%d", &element);
    position = BinarySearching(arr, limit, element);
    if(position == -1)
    {
        printf("Element %d Not Foundn", element);
    }
    else
    {
        printf("Element %d Found at Position %dn", element, position + 1);
    }
    return 0;
}
int BinarySearching(int arr[], int max, int element)
{
    int low = 0, high = max - 1, middle;
    while(low <= high)
    {
        middle = (low + high) / 2;
        if(element > arr[middle])
        low = middle + 1;
        else if(element < arr[middle])
        high = middle - 1;
        else
        return middle;
    }
    return -1;
}



/***********************************************/
/*Binary search using function and pointers*/
#include<stdio.h>
#include<stdlib.h>
int c=0;
int binarysearch(int *,int,int);
int main()
{
    
    int *a,i,n,m,pos;
    
    printf("Enter the size of an array: ");
    scanf("%d",&n);
    a=(int*)malloc(n*sizeof(int));
    
    printf("Enter the elements in ascending order: ");
    for(i=0;i<n;i++)
    {
        scanf("%d",(a+i));
    }
    
    printf("Enter the number to be search: ");
    scanf("%d",&m);
    pos=binarysearch(a,m,n);
    
    if(c==0)
    printf("The number is not found.n");
    else
    printf("The number is found at position %dn",pos+1);
    
    return 0;
}
int binarysearch(int *a,int item,int n)
{
    
    int lower,upper,mid;
    lower=0,upper=n-1;
    while(lower<=upper)
    {
        mid=(lower+upper)/2;
        if(item==a[mid])
        {
            c=1;
            break;
        }
        else if(item<a[mid])
        {
            upper=mid-1;
        }
        else
        lower=mid+1;
    }
    return mid;
}
Posted by at
Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)