# David J Nevin+= Code

Last updated: Jun 27, 2022

# Binary Search

The divide and conquer search method.

The sequential searching through all data entries one by until until we find a match.

Time complexity is O(n).

 ``````100 101 102 103 104 `````` ``````def linear_search(data, target): for i in range(len(data)): if data[i] == target: return True return False ``````

The worst-case runtime of a linear search would be O(n).

## Binary Search (Iterative)

Note: assumes that the array on which the search will take place is sorted in ascending order. We start in the middle of the data. If the result is our search term when we finish searching. If not, and is smaller than the target we repeat the process on the upper half of the data, otherwise if the middle is larger than the target search the lower half.

In each case we pick a new mid point and choose to search either the upper half or lower half of the data. This is of course much more efficient than an iterative.

 ``````100 101 102 103 104 105 106 107 108 109 110 111 112 `````` ``````def binary_search_iterative(data, target): low = 0 high = len(data) - 1 while low <= high: mid = (low + high) // 2 if target == data[mid]: return True elif target < data[mid]: high = mid - 1 else: low = mid + 1 return False ``````

The worst-case time complexity of a binary search is O(logn).

## Binary Search (Recursive)

 ``````100 101 102 103 104 105 106 107 108 109 110 `````` ``````def binary_search_recursive(data, target, low, high): if low > high: return False else: mid = (low + high) // 2 if target == data[mid]: return True elif target < data[mid]: return binary_search_recursive(data, target, low, mid-1) else: return binary_search_recursive(data, target, mid+1, high) ``````

Next: Binary Search Extended
Previous: Hashing First Steps