int binary_search(List a, int l, int r, int x) {
if (r >= l) {
int middle = (l + (r - l) / 2).toInt();
//If the element is present at middle
if (a[middle] == x) {
return middle;
}
//If the element is smaller than middle
if (a[middle] > x) {
return binary_search(a, l, middle - 1, x);
}
return binary_search(a, middle + 1, r, x);
}
return -1;
}
void main() {
List list = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89];
int x = 55;
int n = list.length;
int index = binary_search(list, 0, n - 1, x);
print('list:');
print(list);
if (index != -1) {
print('$x found at positions: $index');
} else {
print('$x Not found');
}
}
Given a sorted array of n elements, write a function to search for the index of a given element (target)
O(log n) Worst Case
O(1) Best Case (If middle element of initial array is the target element)
O(1) For iterative approach
O(1) For recursive approach if tail call optimization is used, O(log n) due to recursion call stack, otherwise
arr = [1,2,3,4,5,6,7]
target = 2
Initially the element at middle index is 4 which is greater than 2. Therefore we search the left half of the
array i.e. [1,2,3].
Here we find the middle element equal to target element so we return its index i.e. 1
target = 9
A simple Binary Search implementation may return -1 as 9 is not present in the array. A more complex one would return the index at which 9 would have to be inserted, which would be `-8` (last position in the array (7) plus one (7+1), negated)`.
A CS50 video explaining the Binary Search Algorithm