Algorithms: Binary Search

Question 1

Which is more efficient: linear search or binary search?

Answer 1

binary search is more efficient as we are able to leverage a divide and conquer strategy. We compare the target element to the middle element of the array. If the target element is less than the middle element, then we are able to ignore the right of the array. Repeating this same strategy until we find out target element or determine that the element is not present.

Question 2

What is the bisect module?

Answer 2

Bisect is a built-in binary search module in Python that takes in a sorted array of integers and a key, and returns the index of the first occurrence of that key from the array

Question 3

What does bisect_left do?

Answer 3

bisect_left is a method of the bisect module which returns the index of the left-most occurrence of the key

Question 4

What does bisect_right do?

Answer 4

bisect_right is a method of the bisect module which returns the index to the right of the key element. This is used to serve as an insertion point.

Question 5

What does the bisect function do?

Answer 5

bisect is equivalent in functionality to bisect_right

Question 6

What is the purpose of insort_left and insort_right?

Answer 6

the purpose is to maintain the sorting of a list when inserting a new element. These both operate similarly to bisect_left and bisect_right, respectively. The difference in functionality is that insort INSERTS an element into the list whereas bisect returns the index of a target element

Question 7

What is a cyclically shifted array?

Answer 7

an array that is able to become sorted by shifting its elements cyclically