Binary Search

This searching technique is applied on sorted list. First calculate mid point then follow the following procedure

1. Check whether a[mid] and key are equal , if condition is true print the position, if this is false

2.Compare whether key is greater than a[mid] ,if this is true update l to mid+1 and repeat the above procedure, if this is false

3. Update h to mid -1 and repeat the above procedure.

4. If all the above conditions are false print 'key not found'

Source Code: 

a=[]

flag=0

n=int(input("enter how many number of elements"))

for i in range(n):

    a.append(int(input()))

print("List is:\n")

print(a)

key=int(input("enter key"))

l=0

h=n-1

while l<=h:

    mid=(l+h)//2

    if key==a[mid]:

        flag=1

        break

    elif key>a[mid]:

        l=mid+1

    else:

        h=mid-1

if flag==1:

    print("%d found at %d position" %(key,mid))

else:

    print("%d not found" %key)

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32

Type "copyright", "credits" or "license()" for more information.

>>> ================================ RESTART ================================

>>> 

enter how many number of elements5

1

2

3

4

5

List is:

[1, 2, 3, 4, 5]

enter key10

10 not found

>>> ================================ RESTART ================================

>>> 

enter how many number of elements5

1

2

3

4

5

List is:

[1, 2, 3, 4, 5]

enter key1

1 found at 0 position

>>> ================================ RESTART ================================

>>> 

enter how many number of elements5

1

2

3

4

5

List is:

[1, 2, 3, 4, 5]

enter key2

2 found at 1 position

>>> ================================ RESTART ================================

>>> 

enter how many number of elements5

1

2

3

4

5

List is:

[1, 2, 3, 4, 5]

enter key5

5 found at 4 position

>>>