Binary Search¶
Binary Search is an efficient algorithm for finding an element’s position in a sorted list. It repeatedly divides the search space in half by comparing the target element with the middle element of the sorted list.
Time Complexity: O(log n) - Binary Search halves the search space in each iteration, resulting in a logarithmic time complexity.
Space Complexity: O(1) - Binary Search does not require any additional space.
Code implementation:
1 def binary_search(arr, target):
2 low = 0
3 high = len(arr) - 1
4
5 while low <= high:
6 mid = (low + high) // 2
7 if arr[mid] == target:
8 return mid
9 elif arr[mid] < target:
10 low = mid + 1
11 else:
12 high = mid - 1
13
14 return -1
1 function binarySearch(arr, el, compare_fn) {
2 let m = 0;
3 let n = arr.length - 1;
4 while (m <= n) {
5 let k = (n + m) >> 1;
6 let cmp = compare_fn(el, arr[k]);
7 if (cmp > 0) {
8 m = k + 1;
9 } else if(cmp < 0) {
10 n = k - 1;
11 } else {
12 return k;
13 }
14 }
15 return ~m;
16 }