Binary Search
Dr Rob Blair
[email protected] SCI 2.19
1
Objectives
introduce a divide and conquer technique
understand how to exploit knowledge of the data
2
Binary Search Specification
return true if key is in array of values, else false
3
Binary Search Inputs
array of n values, sorted in non-descending order
element key
4
Binary Search Outputs
boolean - true if key found, else false
5
Binary Search Description
1.Compare key with the middle element.
2.If key matches with middle element, we return true.
3.Else if key is greater than the mid element, search right half.
4.Else (key is smaller) search left half.
6
4 9 9 10 12 15 22 23 24 27
7
10
4 9 9 10 12 15 22 23 24 27
8
10
4 9 9 10 12 15 22 23 24 27
9
10
4 9 9 10 12 15 22 23 24 27
10
10
4 9 9 10 12
11
10
4 9 9 10 12
12
10
4 9 9 10 12
13
10
10 12
14
10
10 12
15
10
16
Pseudo Code
17
binary_search(key, values):
start, end := 0, n
while start <= end:
mid := (start + end) / 2
if key == values[mid]:
return true
else if key < values[mid]:
end = mid - 1
else:
start = mid + 1
return false
18
binary_search(key, values):
start, end := 0, n
while start <= end:
mid := (start + end) / 2
if key == values[mid]:
return true
else if key < values[mid]:
end = mid - 1
else:
start = mid + 1
return false
19
binary_search(key, values):
start, end := 0, n
while start <= end:
mid := (start + end) / 2
if key == values[mid]:
return true
else if key < values[mid]:
end = mid - 1
else:
start = mid + 1
return false
20
binary_search(key, values):
start, end := 0, n
while start <= end:
mid := (start + end) / 2
if key == values[mid]:
return true
else if key < values[mid]:
end = mid - 1
else:
start = mid + 1
return false
21
binary_search(key, values):
start, end := 0, n
while start <= end:
mid := (start + end) / 2
if key == values[mid]:
return true
else if key < values[mid]:
end = mid - 1
else:
start = mid + 1
return false
22
binary_search(key, values):
start, end := 0, n
while start <= end:
mid := (start + end) / 2
if key == values[mid]:
return true
else if key < values[mid]:
end = mid - 1
else:
start = mid + 1
return false
23
binary_search(key, values):
start, end := 0, n
while start <= end:
mid := (start + end) / 2
if key == values[mid]:
return true
else if key < values[mid]:
end = mid - 1
else:
start = mid + 1
return false
24
Binary Search Recursive
25
bin_search(key, values, start, end):
if start > end:
return false
mid := (start + end) / 2
if key == values[mid]:
return true
if key < values[mid]:
return bin_search(key, values, start, mid-1)
else:
return bin_search(key, values, mid+1, end)
26
bin_search(key, values, start, end):
if start > end:
return false
mid := (start + end) / 2
if key == values[mid]:
return true
if key < values[mid]:
return bin_search(key, values, start, mid-1)
else:
return bin_search(key, values, mid+1, end)
27
bin_search(key, values, start, end):
if start > end:
return false
mid := (start + end) / 2
if key == values[mid]:
return true
if key < values[mid]:
return bin_search(key, values, start, mid-1)
else:
return bin_search(key, values, mid+1, end)
28
bin_search(key, values, start, end):
if start > end:
return false
mid := (start + end) / 2
if key == values[mid]:
return true
if key < values[mid]:
return bin_search(key, values, start, mid-1)
else:
return bin_search(key, values, mid+1, end)
29
bin_search(key, values, start, end):
if start > end:
return false
mid := (start + end) / 2
if key == values[mid]:
return true
if key < values[mid]:
return bin_search(key, values, start, mid-1)
else:
return bin_search(key, values, mid+1, end)
30
Time Complexity
31
Time Complexity
n
1= x
2
32
Time Complexity
x
2 =n
33
Time Complexity
x
log2(2 ) = log2(n)
34
Time Complexity
x
log2(2 ) = log2(n)
x × log2(2) = log2(n)
35
Time Complexity
x
log2(2 ) = log2(n)
x × log2(2) = log2(n)
x = log2(n)
36
Time Complexity
(log2(n))
𝒪
37
Time Complexity
same for recursive and iterative methods
just a choice of implementation...
38
