# 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
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 "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

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]:
''