Searching—Finding the specified record(s) in a given data structure on the basis of a given key value. Binary search is the method used for searching. For Example there are 100 employees working in the company and we have to give the increment only that employee whose employee number is 101, so this operation can be used to find the employee detail with employee number 101.
In case of Binary search the first need is to sort the data in array due to binary search work on sorted array. With the help of sorted element array we can search required data from the array very quickly.
In binary search the array list is divided into 2 equal parts.
- Suppose that the elements of array are in ascending order then if the desired element is less than the middle element of array list, it will never be present in the second half of the array.
- Similarly if it is greater than the middle element of array, it will never be present in the first half.
- So, we can search element from only one half of the array list.
- This process is repeated and in the next stage we have to search the element only in one quarter of the array.
- This process reduces the length of the search and search time.
- The process is repeated again & again until the element is found(search is successful or element not found, search is unsuccessful).
- Binary search is extremely efficient search algorithm, that can be used to find the location of a given element data in the array list.
SA, LBD, UBD, ITEM, LOC, BEGN, END, MID
SA…..is Sorted Array
LBD…..is Lower Bound
UBD….is Upper Bound
ITEM…. Stores the value to be searched.
BEGN…..beginning location of array SA
END…..end location of array SA
MIDDLE…..middle location of array SA
This algorithm finds the location(LOC) of ITEM in a on successful search or sets LOC=NULL on unsuccessful search.
Step 1: Set BEGN :=LBD, END:=UBD & MID=INT((BEGN+END)/2).
Step 2: Repeat Steps 3 and 4 while BEGN<=END and SA[MID]!=ITEM.
Step 3: If ITEM<SA[MID] then (ITEM exist in left sub array)
Else (ITEM exist in right sub array)
Step 4: Set MID:=INT((BEGN+END)/2).
Step 5: If SA[MID]=ITEM then (Search is successful)
Set LOC:=NULL. (Search is unsuccessful)
Step 6: Return LOC.
Program to search an item using BINARY SEARCH
#define N 10
int a[N], itemm, begn, endd, midd;
printf("enter %d element of an array",N);
printf("enter item to be search");
printf("\n item %d not found",itemm);
printf("\n item %d found at %d location",itemm,midd+1);
TIME COMPLEXITY OF BINARY SEARCH
- In this case the list is divided into 2 parts and every time our searching is reduced to one part of the list.
- Only one comparison is required when list is having N items, then next comparison is when elements become equal to N/2 ,then next when elements become equal to N/4 and so on till the elements reduce to 1.
- Hence the TIME COMPLEXITY is O(log n) for worst case and O((log n)/2) for average case log n<n for all n>=1.
- Hence, binary search is faster as compared to linear search.
- The only disadvantage for binary search is that the list must be sorted to search an element.
- Binary search method is useful when the list is large.
- This method is faster than linear search because as the list is divided into 2 halves, the number of comparisons or searches is less.
- It takes very less time as compared to linear search(O(log2 n)
The only disadvantage of this method is that the array or the list needs to be sorted before hand.
APPLICATION OF SEARCHING.
- Search engines
- Online enquiry
- Text pattern
- Finding a record from database
- Spell check utility in Word.