Binary Search: What It is and How to Implement It

Binary search is an important algorithm for computer programmers to know because it is a very efficient way to search for an element in a sorted list. The time complexity of binary search is O(log n). This makes binary search much faster than other search algorithms, such as linear search, which has a time complexity of O(n).

What's a Binary Search

Binary search is a divide-and-conquer algorithm that searches for a target in an array by splitting the array until a target is found.

The array is sorted. Binary searches are much faster than doing a simple search since binary search algorithms have a time complexity of O(log n).

Examples and Usage

• Guess the number game

• Finding the minimum and maximum value of an array

• Finding the first occurrence of a value in an array

• Finding the last occurrence of a value in an array

• Sorting an array

The Approach

So the approach is that you would have three pointers: low, high, and middle.

Low - initially 0. This will increase in value if the value in the middle of the array is smaller than the target.

High - initially the length of the input array minus 1. This will decrease in value if the middle of the array is greater than the target.

Middle - low + high / 2. This is the pointer that is being used to see if the middle element of the array is equal to the target. The value of this variable will be returned if it is equal to the target. The value will of course change as the values of low and high change as well.

You have to keep comparing the value of the middle element to the target while the low is less than or equal to the high until you find the target. If no target is found, -1 is returned.

The Solution(Iteratively and Recursively)

//Iterative Approach
binarySearch(items, target) {

    //Sort the input array(items)
    Arrays.sort(items)
    // Initialize two variables, low and high 
    low = 0;
    high = length of items minus 1

    while(low is less than or equal to high) {
        middle = (low + high) / 2;

        if(middle element is equal to target) {
            return middle;
        } else if(middle element < target) {
            low = middle + 1;
        } else {
            high = middle - 1;
        }
    }

    return -1, because the target was not found
}

Recursive Approach

binarySearch(nums, target) {
    nums.sort()

    searchRecursively(nums, target, 0, nums.length - 1
}

public int searchRecursively(int[] nums, int target, int low, int high) {

        if(high is greater than or equal to low)
        {
            middle = (low + high) / 2;

            if(middle element is equal to target) {
                return middle;
            }
            else if(middle element is less than the target {
                return searchRecursively(nums, target, middle + 1, high);
            }
            else return searchRecursively(nums, target, low, middle - 1);
        }

        return -1 since target could not be found.
    }

Iterative Approach

//iterative approach
int binarySearch(int[] items, target) {
    Arrays.sort(items);

    int low = 0, high = items.length - 1;

    while(low <= high) {
       int middle = (low + high) / 2;

        if(items[middle] == target) return middle;
        else if(items[middle] < target) low = middle + 1;
        else high = middle - 1;
    }

    return -1;
}

Recursive Approach O(log n)

public int search(int[] nums, int target) {
    Arrays.sort(nums);
    return searchRecursively(nums, target, 0, nums.length - 1);
}

public int searchRecursively(int[] nums, int target, int low, int high) {
    if(right >= low) {
        int middle = (low + right) / 2;

        if(nums[middle] == target) {
            return middle;
        } else if(nums[middle] < target) {
            return searchRecursively(nums, target, middle + 1, right);
        } else {
            return searchRecursively(nums, target, low, middle - 1);
        }
    }

    return -1   
}