Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Binary Search
EXPLANATION
Binary search is a search algorithm that finds the position of a target value within a sorted array
...
If the target value is equal to the middle element, the algorithm returns its index
...


There are two ways to implement binary search: iteratively and recursively
...

 The algorithm then calculates the middle element of the array, which is the element at
index (low + high) // 2
...

o If the target value is equal to the middle element, the algorithm returns its index
...

o If the target value is greater than the middle element, the algorithm sets the low
pointer to the middle element + 1 and continues the search in the upper half of the
array
...


The time complexity of the binary search technique is O(log n), n being the size of the array
...


The advantages of binary search are:
 Very efficient, with a time complexity of O(log n)
...


The disadvantages of binary search are:
 Only useful for sorted arrays
...


Overall, binary search is a very efficient search algorithm that is well-suited for finding
elements in sorted arrays

---