Binary Search is also known as logarithmic search and half-interval
search. Unlike Linear search, it works on sorted arrays or list. Binary
search begins by comparing
the middle element of the array with the target value. If the target
value (element to be found) matches the middle element, its position in
the array is returned.
If the target value is less than or greater than the middle element,
the search continues in the lower or upper half of the array,
respectively, eliminating the other half from consideration.

Time complexity of Binary Search is

arr[]= { 24, 45, 67, 89, 90, 92, 94, 96 }

Let the element to be found = x = 45

Now,

end = 8

beg = 1

mid = (beg+end)/2 = 4 (floor value) //During implementation please take care of index

Now, we will check if

Therefore we will update end and now end will become

target element in the first half and second half of the array will be eliminated.

Now in first half,

Time complexity of Binary Search is

**O(log n)**where n is the number of elements in the array.**For example:**arr[]= { 24, 45, 67, 89, 90, 92, 94, 96 }

Let the element to be found = x = 45

Now,

end = 8

beg = 1

mid = (beg+end)/2 = 4 (floor value) //During implementation please take care of index

**'0'**Now, we will check if

**arr[3]=x**. Since,**arr[4]=89**which is greater than**x**Therefore we will update end and now end will become

**3**(end=mid - 1). Now we will check for thetarget element in the first half and second half of the array will be eliminated.

Now in first half,

**mid=(beg+end)/2**= (1+3)/3 = 2 . Since arr[mid] = arr[2] = 45= x, it will return true.**Algorithm**
set: beg=1, set: end=len(listing) /*n is the number of elements in the array */

set: mid=(beg+end)/2

If element<arr[beg] or element>arr[end]:

return false

Else:

do While beg<=end:

If arr[mid]=element:

return true

Else:

If arr[mid]>element:

set: end=mid-1

Else:

set: beg=mid+1

End IfElse

End IfElse

End While loop

End IfElse

set: mid=(beg+end)/2

If element<arr[beg] or element>arr[end]:

return false

Else:

do While beg<=end:

If arr[mid]=element:

return true

Else:

If arr[mid]>element:

set: end=mid-1

Else:

set: beg=mid+1

End IfElse

End IfElse

End While loop

End IfElse

**Program:**

def binary_search(element): beg=0 end=len(listing)-1 mid=(beg+end)//2 while beg<=end: if listing[mid]==element: return mid else: if listing[mid]>element: end=mid-1 else: beg=mid+1 mid=(beg+end)//2 return -1 global listing listing=[] print("\nEnter the elements: \n") listing=list(map(int,raw_input().split())) print("Enter the element you want to search: "); element=int(input()) result=binary_search(element) if result==-1: print("\nElement is not present in the array") else: print('\nElement '+str(element)+' is present at index '+str(result))

**OUTPUT:**

**See also:**Implementation of Binary Search in C

EmoticonEmoticon