Binary Search

If we have an ordered list and we know how many things are in the list (i.e., number of records in a file), we can use a different strategy.
• The binary search gets its name because the algorithm continually divides the list into two parts

Searching Technique-Binary Search

• Can be used only for ordered list of items
• Binary search follows the following steps:

 Examines the element in the middle of the array. Is it the sought item? If so, stop searching. Is the middle element too small? Then start looking in second half of array. Is the middle element too large? Then begin looking in first half of the array.
 Repeat the process in the half of the list, that should be examined next.
 Top when item is found, or when there is nowhere else to look and it has not been located

How a Binary Search Works?


Searching Technique-Binary Search


Input: an ordered sequence { a0, a1,a2,…,an} and target value x

Output: an index value i(i.e. position where the target value is located) or -1 to represent there is no such element

1.Let p=0 and q=n-1
2.Repeat step 2-5 while p<=q
3.Let i=(p+q)/2
4.If ai=x, return i
5.If ai< x, let p = i+1; otherwise let q = i-1
6.Return -1



Leave a Reply

Your email address will not be published.