Binary Search

Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array.

If the value of the search key is less than the item in the middle of the interval, narrow the interval to the first half.
Otherwise narrow it to the second half.
Repeatedly check until the value is found or the interval is empty.

Program:

t=input().split()
s=input()
def binarysearch(t,s):
  min=0
  max=len(t)-1
  while max >= min:
    m=min+max // 2
    if t[m] < s:
      min=m+1 
    elif t[m] >s:
      max=m-1
    else:
      return m
  return -1
    
result=binarysearch(t,s)
if result >= 0:
  print("Element found at ",result)
else:
  print("Element not found")
  
Input:
1 2 3 4 5
3
Output:
Element found at 2

Linear Search

Unit - IV

References

Allen B. Downey, “Think Python: How to Think Like a Computer Scientist‘‘, 2nd edition, Updated for Python 3, Shroff/O‘Reilly Publishers, 2016 (http://greenteapress.com/wp/thinkpython/)
Guido van Rossum and Fred L. Drake Jr, ―An Introduction to Python – Revised and updated for Python 3.2, Network Theory Ltd., 2011.
John V Guttag, ―Introduction to Computation and Programming Using Python‘‘, Revised and expanded Edition, MIT Press , 2013
Robert Sedgewick, Kevin Wayne, Robert Dondero, ―Introduction to Programming in Python: An Inter-disciplinary Approach, Pearson India Education Services Pvt. Ltd., 2016.
Timothy A. Budd, ―Exploring Python‖, Mc-Graw Hill Education (India) Private Ltd.,, 2015. 4. Kenneth A. Lambert, ―Fundamentals of Python: First Programs‖, CENGAGE Learning, 2012.
Charles Dierbach, ―Introduction to Computer Science using Python: A Computational Problem-Solving Focus, Wiley India Edition, 2013.
Paul Gries, Jennifer Campbell and Jason Montojo, ―Practical Programming: An Introduction to Computer Science using Python 3‖, Second edition, Pragmatic Programmers, LLC, 2013.