Binary Search
Problem of Search
arr = 3 5 12 2 16 3 174 265 326 517 53 8 64 9
0 1
Problem of Search
arr = 3 5 12 2 16 3 174 265 326 517 53 8 64 9
0 1
• Inputs: (i) an array whose elements are in the
ascending order and (ii) a key.
• Goal: Search for the key in the array. If found, return
its index; if not found, return -1.
Problem of Search
arr = 3 5 12 2 16 3 174 265 326 517 53 8 64 9
0 1
Example 1:
• Search for the element 53.
• Return 8.
Problem of Search
arr = 3 5 12 2 16 3 174 265 326 517 53 8 64 9
0 1
Example 2:
• Search for the element 9.
• Return -1.
Example: key=26
arr = 3 5 12 2 16 3 174 265 326 517 53 8 64 9
0 1
left=0 right=9
Example: key=26
arr = 3 5 12 2 16 3 174 265 326 517 53 8 64 9
0 1
left=0 right=9
• mid ← left + right /2 .
• If arr[mid]==key ==> return mid.
• If arr[mid]>key ==> right ⃪ mid-1.
• If arr[mid]<key ==> left ⃪ mid+1.
Example: key=26
arr = 3 5 12 2 16 3 174 265 326 517 53 8 64 9
0 1
left=0 mid=4 right=9
• mid ← left + right /2 .
• If arr[mid]==key ==> return mid.
• If arr[mid]>key ==> right ⃪ mid-1.
• If arr[mid]<key ==> left ⃪ mid+1.
Example: key=26
arr = 3 5 12 2 16 3 174 265 326 517 53 8 64 9
0 1
left=0 mid=4 right=9
• mid ← left + right /2 .
• If arr[mid]==key ==> return mid.
• If arr[mid]>key ==> right ⃪ mid-1.
• If arr[mid]<key ==> left ⃪ mid+1.
Example: key=26
arr = 3 5 12 2 16 3 174 265 326 517 53 8 64 9
0 1
left=0 mid=4 right=9
• mid ← left + right /2 .
• If arr[mid]==key ==> return mid.
• If arr[mid]>key ==> right ⃪ mid-1.
• If arr[mid]<key ==> left ⃪ mid+1.
Example: key=26
arr = 3 5 12 2 16 3 174 265 326 517 53 8 64 9
0 1
left=5 right=9
• mid ← left + right /2 .
• If arr[mid]==key ==> return mid.
• If arr[mid]>key ==> right ⃪ mid-1.
• If arr[mid]<key ==> left ⃪ mid+1.
Example: key=26
arr = 3 5 12 2 16 3 174 265 326 517 53 8 64 9
0 1
left=5 right=9
• mid ← left + right /2 .
• If arr[mid]==key ==> return mid.
• If arr[mid]>key ==> right ⃪ mid-1.
• If arr[mid]<key ==> left ⃪ mid+1.
Example: key=26
arr = 3 5 12 2 16 3 174 265 326 517 53 8 64 9
0 1
left=5 mid=7 right=9
• mid ← left + right /2 .
• If arr[mid]==key ==> return mid.
• If arr[mid]>key ==> right ⃪ mid-1.
• If arr[mid]<key ==> left ⃪ mid+1.
Example: key=26
arr = 3 5 12 2 16 3 174 265 326 517 53 8 64 9
0 1
left=5 mid=7 right=9
• mid ← left + right /2 .
• If arr[mid]==key ==> return mid.
• If arr[mid]>key ==> right ⃪ mid-1.
• If arr[mid]<key ==> left ⃪ mid+1.
Example: key=26
arr = 3 5 12 2 16 3 174 265 326 517 53 8 64 9
0 1
left=5 mid=7 right=9
• mid ← left + right /2 .
• If arr[mid]==key ==> return mid.
• If arr[mid]>key ==> right ⃪ mid-1.
• If arr[mid]<key ==> left ⃪ mid+1.
Example: key=26
arr = 3 5 12 2 16 3 174 265 326 517 53 8 64 9
0 1
left=5
right=6
• mid ← left + right /2 .
• If arr[mid]==key ==> return mid.
• If arr[mid]>key ==> right ⃪ mid-1.
• If arr[mid]<key ==> left ⃪ mid+1.
Example: key=26
arr = 3 5 12 2 16 3 174 265 326 517 53 8 64 9
0 1
left=5
right=6
• mid ← left + right /2 .
• If arr[mid]==key ==> return mid.
• If arr[mid]>key ==> right ⃪ mid-1.
• If arr[mid]<key ==> left ⃪ mid+1.
Example: key=26
mid=5
arr = 3 5 12 2 16 3 174 265 326 517 53 8 64 9
0 1
left=5
right=6
• mid ← left + right /2 .
• If arr[mid]==key ==> return mid.
• If arr[mid]>key ==> right ⃪ mid-1.
• If arr[mid]<key ==> left ⃪ mid+1.
Example: key=26
mid=5
arr = 3 5 12 2 16 3 174 265 326 517 53 8 64 9
0 1
• mid ← left + right /2 .
• If arr[mid]==key ==> return mid.
• If arr[mid]>key ==> right ⃪ mid-1.
• If arr[mid]<key ==> left ⃪ mid+1.
Time Complexity
• Each iteration reduces the size of array by half.
• Let 𝑛 be the size of the array.
• The total number of iterations is at most log 3 𝑛.
• Per-iteration time complexity: 𝑂 1 .
Overall time complexity: 𝑂 log 𝑛 .
int search(int arr[], int left, int right, int key) {
while (left <= right) {
int mid = (left + right) / 2;
if (key == arr[mid])
return mid; // key is found
if (key > arr[mid])
left = mid + 1; // search in the right half
else
right = mid - 1; // search in the left half
}
return -1; // key is not found
}
int search(int arr[], int left, int right, int key) {
while (left <= right) {
int mid = (left + right) / 2;
if (key == arr[mid])
return mid; // key is found
if (key > arr[mid])
left = mid + 1; // search in the right half
else
right = mid - 1; // search in the left half
}
return -1; // key is not found
}
int search(int arr[], int left, int right, int key) {
while (left <= right) {
int mid = (left + right) / 2;
if (key == arr[mid])
return mid; // key is found
if (key > arr[mid])
left = mid + 1; // search in the right half
else
right = mid - 1; // search in the left half
}
return -1; // key is not found
}
int search(int arr[], int left, int right, int key) {
while (left <= right) {
int mid = (left + right) / 2;
if (key == arr[mid])
return mid; // key is found
if (key > arr[mid])
left = mid + 1; // search in the right half
else
right = mid - 1; // search in the left half
}
return -1; // key is not found
}
int search(int arr[], int left, int right, int key) {
while (left <= right) {
int mid = (left + right) / 2;
if (key == arr[mid])
return mid; // key is found
if (key > arr[mid])
left = mid + 1; // search in the right half
else
right = mid - 1; // search in the left half
}
return -1; // key is not found
}
int search(int arr[], int left, int right, int key) {
while (left <= right) {
int mid = (left + right) / 2;
if (key == arr[mid])
return mid; // key is found
if (key > arr[mid])
left = mid + 1; // search in the right half
else
right = mid - 1; // search in the left half
}
return -1; // key is not found
}
How to support both search and insertion?
Vector
v = 3 5 12 16 17 26 32 51 53
• The ascending order must be kept; otherwise, search would
take 𝑂 𝑛 time.
• Inserting an item into the middle has 𝑂 𝑛 time complexity
(on average).
Vector
v = 3 5 12 16 17 26 32 51 53
To insert: 8
• The ascending order must be kept; otherwise, search would
take 𝑂 𝑛 time.
• Inserting an item into the middle has 𝑂 𝑛 time complexity
(on average).
Vector
v = 3 5 12 16 17 26 32 51 53
To insert: 8
• The ascending order must be kept; otherwise, search would
take 𝑂 𝑛 time.
• Inserting an item into the middle has 𝑂 𝑛 time complexity
(on average).
List
7 22 25 39 41 68
left mid right
• Can we perform binary search in the list?
• No. Given left and right, we cannot get mid efficiently.
Comparisons
Search Insertion
Vector 𝑂(log 𝑛) 𝑂(𝑛)
List 𝑂(𝑛) 𝑂(1)
Comparisons
Search Insertion
Vector 𝑂(log 𝑛) 𝑂(𝑛)
List 𝑂(𝑛) 𝑂(1)
Skip List 𝑂(log 𝑛) 𝑂(log 𝑛)
Thank You!
