Tag Archives: searching

Binary Search

Binary Search finds the position of a specified value (key)in a sorted array.In each step it discards half of the elements to search , thus the worst case running time of binary search is O(log n).

Binary search follows these simple steps :

1. Compare the middle element of the array with key if middle element is same as key return the index of the middle else go to step 2

2.if middle element greater than key  binary search for the key in the left half of the array (start to middle-1) , if its less  than key binary search for the key in the right half of the array (middle+1 to end) .

3.repeat this till the size of array to search reduces to zero.

 

For more information on binary search visit http://en.wikipedia.org/wiki/Binary_search_algorithm

Below is the C++ code for binary search algorithm.
CODE:

/*

http://randomtechbits.in/

*Program to search a number in a sorted array using BINARY SEARCH
*inputs: N- number of integers to sort ,A-array of integers,NUM -the number to search for     
*output: position of number in the array
*code tested on devc++ IDE
*/
#include<iostream>
#include<conio.h>
using namespace std;

int binarysearch(int A[],int NUM,int low,int high)
{int mid;
if(low>high)return -1;
else mid=low+(high-low)/2;
if(A[mid]==NUM)  return mid;
else if(A[mid]>NUM)  return binarysearch(A,NUM,low,mid-1);
else  return binarysearch(A,NUM,mid+1,high); 
}
main()
{
int N,NUM,pos;
int *A;
int i,j;
cout<<"Enter the number of elements in te sorted array:\n"; cin>>N;
A=new int[N];
cout<<"Enter the array\n";
for(i=0;i<N;i++)   cin>>A[i];
cout<<"Enter the number to search for\n";   cin>>NUM;
pos=binarysearch(A,NUM,0,N);
if(NUM!=-1)
  cout<<"\nNumber found at postion at "<<pos<<" in the array"<<"\n";
else 
  cout<<"\nNumber not found in the array"<<"\n";
//for more codes visit randomtechbits.in
getch();   
}

Searching Algorithms

Searching is the process of finding a particular item may be string,integer or anything else in a list of items.

These algorithms generally involve the comparison of key with the elements in the list and returning element index in the list if a match occurs. The simplest example is consider a list of elements:

LIST :3 5 10 100 6

suppose we are searching for element 6 in this , so we will start comparing 6 with every element in the list starting from 3 , since 6 is present at position 4 in the array so the above search will return 4. Various searching algorithms exist for different datastructures varying in their runtime and technique they are using for finding match.U can find the details of various searching algorithms under this tab along with their code. So keep reading and keep visiting this page.If u are searching for some code which is not here just mail us we will add it.