## Lecture 08. Searching
- Linear (Sequential) Search
- Binary Search and Variants
- Binary Search Tree (BST)
---
### Searching algorithms
- Sequential Search: unsorted arrays
- Interval Search: sorted arrays
- Graph search
---
### Searching algorithms
<img src="https://cdn.ucode.vn/uploads/1/upload/gpuIdQEZ.png"/>
---
### Linear Search
<img src="https://cdn.ucode.vn/uploads/1/upload/qXFBhZRK.png"/>
---
### Linear Search
- The list or array is traversed sequentially and every element is checked.
- Works for unsorted collections
- $O(n)$
---
### Linear Search
```python=
def linear_search(arr, val):
for i in range(len(arr)):
if arr[i] == val:
return i
return -1
```
---
### Binary Search
<img src="https://cdn.ucode.vn/uploads/1/upload/xTryCbGQ.png"/>
---
### Binary Search
- Follows **divide and conquer** methodology
- Requires that the collection be sorted
- Division operations may be slow
- $O(\log n)$
---
### Binary Search
```python=
def binary_search(arr, val):
L, R = 0, len(arr) - 1
while L <= R:
mid = (L + R) // 2
if arr[mid] == val: return mid
if val < arr[mid]: R = mid - 1
else: L = mid + 1
return -1
```
---
### Binary Search: variants
- Jump Search
- Interpolation Search
- Exponential Search
- Fibonacci Search
- Ternary Search
Note:
https://www.tutorialspoint.com/introduction-to-searching-algorithms
---
### Jump Search
<img src="https://cdn.ucode.vn/uploads/1/upload/NkhEtbpE.png" class="element-left content-img" />
---
### Jump Search
- Works on a sorted array
- Divide and conquer approach
- Search in **jumps** instead of sequentially: `arr[0]`, `arr[0+jump]`, `arr[0+2*jump]`, `arr[0+3*jump]`...
- Linear search in matched jump: `arr[i*jump] <= val < arr[(i+1)*jump]`
- Normally: $jump = \sqrt{n}$
- $O(\sqrt{n})$, no division operation
Note:
The single most important advantage of jump search when compared to binary search is that it does not rely on the division operator (/).
---
### Jump Search
```python=
def jump_search(arr, val):
length = len(arr)
jump = sqrt(length)
L, R = 0, 0
while L < length and arr[L] <= val:
R = min(length - 1, L + jump)
if arr[L] <= val and arr[R] >= val:
break
L += jump
if L >= length or arr[L] > val:
return -1
i = L
while i <= R and arr[i] <= val:
if arr[i] == val:
return i
i += 1
return -1
```
---
### Fibonacci Search
<img src="https://cdn.ucode.vn/uploads/1/upload/deXudqpq.png"/>
---
### Fibonacci Search
- Similar to jump search, in which jump sizes are Finonacci numbers
- Maintain the search range between two consecutive Fibonacci numbers $f_1$ and $f_2$, starting from the largest $f_2$ that does not exceed the data size.
- Reduce $f_1$, $f_2$ gradually until $1$.
- Time complexity? No divisions.
Note:
$O(\log n)$ by the nature of fibonacci sequence
---
### Fibonacci Search
```python=
def fibonacci_search(arr, val):
f1, f2 = 0, 1
while f2 < len(arr):
f1, f2 = f2, f1 + f2
f1, f2 = f2 - f1, f1
index = -1
while f2 > 1:
i = min(index + f1, len(arr) - 1)
if arr[i] == val:
return i
if arr[i] < val:
index = i
f1, f2 = f2 - f1, f1
return -1
```
---
### Exponential Search
<img src="https://cdn.ucode.vn/uploads/1/upload/hskUvdzI.png" class="element-left content-img" />
---
### Exponential Search
- Exponential Search : galloping search, doubling search or Struzik search
- Determining the range where the `val` likely to be: using exponential growth of the index
- Using binary search in the found range
- $O(\log n)$
Note:
https://stackabuse.com/search-algorithms-in-python/
Exponential search works better than binary search when the element we are searching for is closer to the beginning of the array.
---
### Exponential Search
```python=
def exponential_search(arr, val):
if arr[0] == val:
return 0
ind = 1
while ind < len(arr) and arr[ind] <= val:
ind = ind * 2
return binary_search(arr[ind//2:min(ind, len(arr))], val)
```
---
### Interpolation Search
- Divide and conquer algorithm, similar to binary search
- Does not always begin searching at the middle, but identify the searching position using **linear interpolation**
- Work best on uniformly distributed, sorted arrays. $O(\log \log n)$
Note:
https://stackabuse.com/search-algorithms-in-python/
---
### Interpolation Search
- Identify the searching position using **linear interpolation**
$i = L + \frac{val - a[L]}{a[R]-a[L]}\times(R-L)$
Note:
https://stackabuse.com/search-algorithms-in-python/
---
### Interpolation Search
```python=
def interpolation_search(a, val):
L, R = 0, len(a) - 1
while L <= R and a[L] <= val <= a[R]:
i = L + int((R - L) * (val - a[L]) / (a[R] - a[L]))
if a[i] == val:
return i
if a[i] < val: L = i + 1
else: R = i - 1
return -1
```
---
### Tenary Search
<img src="https://cdn.ucode.vn/uploads/1/upload/wqeQUkOR.png" class="element-left content-img" />
---
### Tenary Search
- Similar to binary search
- Divide the collection into 3 chunks, instead of 2.
$mid1 = L + \frac{R-L}{3}$
$mid2 = R - \frac{R-L}{3}$
---
### Tenary Search
```python=
def tenary_search(arr, val):
L, R = 0, len(arr) - 1
while L <= R:
mid1, mid2 = L + (R-L) // 3, R - (R-L) // 3
if arr[mid1] == val: return mid1
if arr[mid2] == val: return mid2
if val < arr[mid1]: R = mid1 - 1
elif val > arr[mid2]: L = mid2 + 1
else: L, R = mid1 + 1, mid2 - 1
return -1
```
---
### Binary Search Tree
--> Next lession
---
### Search complexity
<img src="https://cdn.ucode.vn/uploads/1/upload/tdqCgScb.png"/>
---
### Binary Search: upper and lower bound
- `arr = [10, 10, 10, 20, 20, 20, 30, 30]`, `val = 20`
- Upper bound: smallest element that is **greater** than $val$ $\rightarrow 6$
- Lower bound: greatest element that is **not less** than $val$ $\rightarrow 3$
- Equal range: `(3, 5)`
---
### Searching in Python
- Linear Search: `list.index(val)`
- Check for existance:
- `list.count(val)`
- `val in list`
- `val in set`
- `val in dict`
- Binary search
---
### Searching in Python: linear
- `list.index(val)`
- Raises `ValueError` if not found
- `list.index(val, start)`
- `list.index(val, start, end)`
---
### Searching in Python: Binary
- Self implemented
- Using `bisect`
---
### Searching in Python: bisect
- `bisect`: maintained a sorted list
- Implements **bisection** algorithms to find the insertion point for adding a given element in a sorted list
- Can be used for **binary search**
Note:
implements bisection algorithms to find the insertion point for adding a given element in a sorted list
---
### Searching in Python: bisect
- `bisect_left(a, x)`: locate the insertion point for x in a to maintain
- `bisect_right(a, x)`: same, but returns an insertion point which comes **after** any **existing** entries of x in a.
---
### Searching in Python: bisect
- `L = bisect_left(ar, x)`
- `R = bisect_right(ar, x)`
- `ar[L]`: leftmost value exactly equal to `x`
- `ar[L-1]`: rightmost value less than `x`
- `ar[R-1]`: rightmost value less than or equal to `x`
- `ar[R]`: lefttmost value greater than `x`
---
## The End
---
{"metaMigratedAt":"2023-06-17T19:46:11.969Z","metaMigratedFrom":"YAML","title":"Thuc Nguyen's ADSA Course - Lecture 08. Searching","breaks":true,"description":"View the slide with \"Slide Mode\".","slideOptions":"{\"theme\":\"white\"}","contributors":"[{\"id\":\"476f9158-9a39-4a2d-bb09-ce08dd7eb978\",\"add\":8842,\"del\":1038}]"}