FOR FREE CONTENT

Binary search is a searching technique where it is searched that a particular element is present in the array or not. This searching technique is different from the linear search. In this technique, the array should be given in sorted order. First, the middle index is found from the array, the searched element is then compared with the element of that middle index. If the two elements are the same, then the position of the element will be printed. If the searched element is smaller than the element of the middle index then the left subarray will be searched and if the element is greater than the element of the middle index then the right sub-array will be searched. For the sub-arrays again, the same procedure will be followed by finding the middle index. The mechanism of binary search can be explained by an analogy of a telephone directory. When we search for a particular name, we first open the middle page of the directory, and then we decide which part we need to search. This procedure continues till we find the searched contact.

EXAMPLE:

Let the array be:

The array is in sorted order. Suppose the searching element is 82. Now for the first time in this case the lower index is 0, the upper index is 5 - 1= 4 (as the number of elements is 5). Now the middle value will be calculated as: 

mid = (upper index + lower index)/2

        = (4 + 0)/2

        = 2

Now, the element of index 2 is 78 which will be compared with the searched element 82. They are not equal but the searched element is greater than the middle-positioned element. Now, the right sub-array is to be searched. For searching the right sub array the lower index will be set to mid+1. In this case, the lower index will be 2 + 1 = 3, the upper index will remain same i.e. 4. 

So now the array to be searched is:

Now again the middle value will be calculated as:

mid = (upper index + lower index)/2

        = (4 + 3)/2

        = 7/2

        = 3

Therefore, 

Now the value of index 3 (here, 82) will be compared with the searched element (82), as both the elements are the same, which means the searched element is present in the array, the position of the element will be printed. 

If the element is present in the left sub-array then the upper index will be set to mid-1 and the lower index will remain the same.

If the element is not present in the array, then a message “element not found” will be printed.

INPUT: Array elements
OUTPUT: the index of the element if found
PROCESS:
Step 1: [taking the input]
	Read n [number of elements]
	For i=0 to n-1 repeat
		Read a[i]
	[end of ‘for’ loop]
	Read x [the element which is to be searched]
Step 2: [searching the element]
Set l<-0
Set u<-n
While u≥l repeat
	Set mid<-(l+u)/2
 	if (a[mid]=x) then
		 	print "Element x is found at index mid
			break
		[End of ‘if’]
		if (a[mid] > x) then 
			Set u<-mid-1
		[End of ‘if’]
		if(a[mid]<x) then
			Set l<-mid+1
		[End of ‘if’]
	[end of ‘while’]
	If u<l then
		Print "Element not found"
	[End of ‘if’]
Step 3: Stop.