Searching

Use linear search, so compare the key with elements from left to right.

List: $[1,-2,32,8,17,19,42,13,0,44]$

### For key = 8
| Pass | Index | Element | Decision |
|---|---:|---:|---|
| 1 | 0 | 1 | $1 \neq 8$ |
| 2 | 1 | -2 | $-2 \neq 8$ |
| 3 | 2 | 32 | $32 \neq 8$ |
| 4 | 3 | 8 | $8 = 8$, found |

Position found = 4

### For key = 1
| Pass | Index | Element | Decision |
|---|---:|---:|---|
| 1 | 0 | 1 | $1 = 1$, found |

Position found = 1

### For key = 99
| Pass | Index | Element | Decision |
|---|---:|---:|---|
| 1 | 0 | 1 | $1 \neq 99$ |
| 2 | 1 | -2 | $-2 \neq 99$ |
| 3 | 2 | 32 | $32 \neq 99$ |
| 4 | 3 | 8 | $8 \neq 99$ |
| 5 | 4 | 17 | $17 \neq 99$ |
| 6 | 5 | 19 | $19 \neq 99$ |
| 7 | 6 | 42 | $42 \neq 99$ |
| 8 | 7 | 13 | $13 \neq 99$ |
| 9 | 8 | 0 | $0 \neq 99$ |
| 10 | 9 | 44 | $44 \neq 99$ |

Search is unsuccessful.

### For key = 44
| Pass | Index | Element | Decision |
|---|---:|---:|---|
| 1 | 0 | 1 | $1 \neq 44$ |
| 2 | 1 | -2 | $-2 \neq 44$ |
| 3 | 2 | 32 | $32 \neq 44$ |
| 4 | 3 | 8 | $8 \neq 44$ |
| 5 | 4 | 17 | $17 \neq 44$ |
| 6 | 5 | 19 | $19 \neq 44$ |
| 7 | 6 | 42 | $42 \neq 44$ |
| 8 | 7 | 13 | $13 \neq 44$ |
| 9 | 8 | 0 | $0 \neq 44$ |
| 10 | 9 | 44 | $44 = 44$, found |

Position found = 10

The program returns the position of the first matching element it finds.

For the list $[42,-2,32,8,17,19,42,13,8,44]$, the first $8$ occurs at index 3, so the program returns position 4.

This means linear search stops as soon as it finds the first occurrence of the key, even if the same value appears again later in the list.

```python
def linearSearch(lst, key):
for i in range(len(lst)):
if lst[i] == key:
return i + 1
return None

# input list of 10 mixed negative and positive numbers
lst = []
print("Enter 10 integers (negative and positive):")
for _ in range(10):
lst.append(int(input()))

key = int(input("Enter key value: "))
pos = linearSearch(lst, key)

if pos is None:
print("Key is not present in the list")
else:
print("Key is present at position", pos)
```

This program takes 10 integers and a key, searches using linear search, and prints the position if found; otherwise it prints that the key is not present.

```python
def binarySearch(lst, key):
first = 0
last = len(lst) - 1
while first <= last:
mid = (first + last) // 2
if lst[mid] == key:
return mid + 1
elif key < lst[mid]:
last = mid - 1
else:
first = mid + 1
return None

# input list of 10 integers in ascending order
lst = []
print("Enter 10 integers in ascending order:")
for _ in range(10):
lst.append(int(input()))

key = int(input("Enter key value: "))
pos = binarySearch(lst, key)

if pos is None:
print("Key is not present in the list")
else:
print("Key is present at position", pos)
```

### Example results for 3 keys
For a sorted list such as $[3, 8, 12, 15, 21, 27, 34, 40, 56, 72]$:
- key = 15 → present at position 4
- key = 72 → present at position 10
- key = 19 → not present

Binary search works only on a sorted list.

Given list:
$[50,31,21,28,72,41,73,93,68,43,45,78,5,17,97,71,69,61,88,75,99,44,55,9]$

## 1) Linear search on the unsorted list
Linear search compares items from the beginning.

- 1: not present → 24 comparisons
- 5: found at position 13 → 13 comparisons
- 55: found at position 23 → 23 comparisons
- 99: found at position 21 → 21 comparisons

## 2) Sorted list in ascending order
Using sorting, the list becomes:

$[5,9,17,21,28,31,41,43,44,45,50,55,61,68,69,71,72,73,75,78,88,93,97,99]$

## 3) Linear search again on the sorted list
Linear search still checks from the start, so comparisons depend on where the item appears.

- 1: not present → 24 comparisons
- 5: position 1 → 1 comparison
- 55: position 12 → 12 comparisons
- 99: position 24 → 24 comparisons

## 4) Binary search on the sorted list
Binary search uses iterations.

- 1: not present → 5 iterations
- 5: position 1 → 5 iterations
- 55: position 12 → 1 iteration
- 99: position 24 → 5 iterations

## Inference
- In an unsorted list, linear search may need many comparisons.
- In a sorted list, binary search is much faster than linear search.
- Binary search is especially efficient when the key is near the middle.