StatCounter

Sunday, February 14, 2016

Binary search of an ordered list of integers

Binary search is a fundamental algorithm in computer science. It is used to find the position of a given integer in a sorted list of integers. We don't have to iterate through the whole list, if we use this algorithm. Therefore it is an efficient algorithm for searching. The complexity of binary search algorithm is O(logN). 

http://interactivepython.org/runestone/static/pythonds/SortSearch/TheBinarySearch.html

If N elements are there in the list, 
you will have to halve the list x times to find an element. (Halve the list until 1 element is left)

 1 = N / 2x
 2x = N
 x = log2 N

Therefore time complexity - O(logN)

[code]
#include <stdio.h>

int main()
{
    int arr[100];
    int n, i, el;

    printf("Enter the number of elements: ");
    scanf("%d",&n);

    printf("Enter the elements\n");
    for(i = 0; i<n; i++)
    {
        scanf("%d",&arr[i]);
        if(i != 0 && arr[i-1]>arr[i])
        {
            printf("Please enter a sorted list!\n");
            return 0;
        }
    }

    printf("Enter the element to search\n");
    scanf("%d",&el);

    int position = binarySearch(arr,n,el);
   
    if(position != -1)
        printf("The element is at %d.\n",position);
    else
        printf("Element not found!\n");

    return 0;
}

/*Binary search function
  Arguments - integer array
          size of the array
          element to search for
  Return the position if successful
 
*/
int binarySearch(int arr[], int size, int el)
{
    int low = 0, high = size-1;
    int mid = (high + low)/2;

    while(arr[mid] != el)
    {
        if(arr[mid] > el)
            high = mid;
        else
            low = mid;

        if(high == low+1)
        {
            if(arr[high] == el)
                return high;
            else if(arr[low] == el)
                return low;
            else
                return -1;
        }
        mid = (low + high)/2;
    }
    return mid+1;
}[/code]