Binary search.md (947B)
1 +++ 2 title = 'Binary search' 3 template = 'page-math.html' 4 +++ 5 # Binary search 6 an efficient algorithm to search position of element in a *sorted list* 7 8 belongs to the “Divide and Conquer” strategy (divide into subproblems into smallest is solved, solve subproblems recursively, combine all solutions) 9 10 average faster than linear search 11 12 How it works: 13 works by comparing the search key K with the middle element A[m] of the list 14 15 middle element found by: 16 subtract array.length-1, divide by 2, round up 17 18 then: 19 20 - if $K>A[m]$, first half is eliminated 21 - search goes on in the second half of the array 22 - continues recursively 23 - if $K<A[m]$, second half is eliminated 24 - search goes on in the first half of the array 25 - continues recursively 26 27 Performance: 28 29 - Best case: 1 comparison 30 - Worst case: log₂(n+1) comparisons 31 - Average: ~log₂(n) comparisons 32 33 Time complexity: 34 35 - Best case: O(1) 36 - Worst case: O(log(n)) 37 - Average: O(log(n))