Chapter 7: Searching & Hashing

Example 1, page no. 208

In [1]:
import sys

arr = []
opt = 'y'
print "nHow many elements you want to enter in the array: ",
n = int(raw_input())
for i in range(n):
    print "Enter element %d: " %(i+1),
    arr.append(int(raw_input()))
print "\n\nPress any key to continue..."
raw_input()

while (1):
    if opt == 'Y' or opt == 'y':
        print "Enter the element to be searched: ",
        item = int(raw_input())
        found = False
        for i in range(n):
            if (item == arr[i]):
                print "\n%d found at position %d"  %(item,(i+1))
                found = True
                break
        if not found:
            print "Item %d not found in array" %item
        print "Press (Y/y) to continue: ",
        opt = raw_input()
    else:
        sys.exit()
nHow many elements you want to enter in the array: 3
 Enter element 1: 15
 Enter element 2: 10
 Enter element 3: 5
 

Press any key to continue...

Enter the element to be searched: 5
 
5 found at position 3
Press (Y/y) to continue: n
An exception has occurred, use %tb to see the full traceback.

SystemExit
To exit: use 'exit', 'quit', or Ctrl-D.

Example 2, page no. 211

In [2]:
import sys

arr = []
print "How many elements you want to enter in the array ?: ",
n = int(raw_input())
for i in range(n):
    print "Enter element %d: " %(i+1),
    arr.append(int(raw_input()))
print "\nPress any key to continue...",
raw_input()
opt = 'y'
while(1):
    if opt == "Y" or opt == "y":
        print "Enter the element to be searched: ",
        item = int(raw_input())
        start = 0
        end = n - 1
        middle = (start + end)/2
        while(item != arr[middle] and start <= end):
            if (item > arr[middle]):
                start = middle+1
            else:
                end = middle-1
            middle = (start+end)/2
        if (item==arr[middle]):
            print "%d found at position %d" %(item,(middle + 1));
        if (start>end):
            print "%d not found in array" %item
        print "Press (Y/y) to continue: ",
        opt = raw_input()
    else:
        sys.exit()
 How many elements you want to enter in the array ?: 3
 Enter element 1: 15
 Enter element 2: 10
 Enter element 3: 5
 
Press any key to continue...
 Enter the element to be searched: 10
 10 found at position 2
Press (Y/y) to continue: n
An exception has occurred, use %tb to see the full traceback.

SystemExit
To exit: use 'exit', 'quit', or Ctrl-D.

Example 3, page no. 215

In [5]:
class interpolation:
    def InterSearch(self, arr, no):
        Low = 0
        High = no - 1
        print "Enter the Number to be searched: ",
        key = int(raw_input())
        while(Low < High):
            Mid = (Low+(High-Low)) * ((key-arr[Low])/(arr[High]-arr[Low]))
            if (key < arr[Mid]):
                High = Mid-1
            elif (key > arr[Mid]):
                Low = Mid+1;
            else:
                print "The key ", key, " is found at the location ", Mid
                return
        print "\nThe Key " , key, " is NOT found"


ob = interpolation()
print "Enter the number of elements: ",
n = int(raw_input())
a = []
for i in range(n):
    print "Enter element %d: " %(i+1),
    a.append(int(raw_input()))
b = a
ob.InterSearch(b,n);
print "Press any key to continue...",
raw_input()
Enter the number of elements: 3
 Enter element 1: 5
 Enter element 2: 10
 Enter element 3: 15
 Enter the Number to be searched: 15
 The key  15  is found at the location  2
Press any key to continue...
Out[5]:
''

Example 4, page no. 217

In [6]:
def fib(n):
    f1 = 0
    f2 = 1
    for i in range(n):
        temp = f2
        f2 = (f1+f2)
        f1 = temp
    return f2

def fibonacci_search(lst, n, item):
    j = 1
    while(fib(j)<n):
        f1 = fib(j-2)
        j += 1
    f2 = fib(j-3)
    mid = n-(f1+1);
    while (item != lst[mid]):
        if(mid<0 or item > lst[mid]):
            if (f1==1):
                return -1
            mid = mid+f2
            f1 = f1-f2
            f2 = f2-f1
        else:
            if (f2==0):
                return -1
            mid = mid-f2
            t = f1-f2
            f1 = f2
            f2 = t
    return mid
        
lst = []
print "Enter the total number of list: ",
n = int(raw_input())
print "Enter the elements in the list "
for i in range(n):
    print "Input number ", i+1, ": ",
    lst.append(int(raw_input()))
print "Enter the number to be searched: ",
item = int(raw_input())
loc = fibonacci_search(lst, n, item)
if (loc != -1):
    print "The number is in the list..."
else:
    print "The number is not in the list..."
raw_input()
Enter the total number of list: 3
 Enter the elements in the list 
Input number  1 : 5
 Input number  2 : 10
 Input number  3 : 15
 Enter the number to be searched: 10
 The number is in the list...

Out[6]:
''