Algorithm gymnastics 1

Binary Search on Arrays

Description

An Array to store the sorted integers and the key you are looking for are passed, and if that key is in an Array, it returns the Index of the key. If the key does not exist, -1 is returned.

Example

Array with 47 keys and 20 elements

Solution

Runtime Complexity: O(logn) Memory Complexity: O(logn)

Binary Search is used to find the index of an element in a sorted array. If the element does not exist, it can be found as efficiently as it does. The algorithm divides the input array in half at each step. After every step, you can discard half of the array to see if the index you are looking for is found. Therefore, the solution can be calculated in O (logn) time.

Rough algorithm flow

1. Determine the low of the smallest index and the high of the largest index, which are the range to be examined by Array.
2. Find the value of mid at the midpoint from the low and high.
3. If the element in the index of mid is the same as the key, return mid.
4. If it is larger than the element in the index of mid, high = mid -1. (Low remains as it is)
5. If it is smaller than the element in the index of mid, low = mid + 1. (High remains the same)
6. However, if low becomes larger than high, the key does not exist, so -1 is returned.

code

Supplement

The Iterative method using While loop instead of Recursive has the same speed efficiency, but Space Complexity can be O (1).