Binary Search Technique

When to use: Used for searching for an element in a sorted list or array. Reduces the time complexity from O(n) to O(log n).

Conditions:
Input must be sorted.

Steps:

1. Set the left index = 0, right index = length – 1.
2. Get middle index: (left – right) / 2. Make sure that middle index is inside the iteration so it can change and calculate for every left and right index.
3. Check if middle element is equal to the target, if it is return and end search.
4. If middle element is less than target, search right side of the list. Set the left index to be at the middle + 1.
5. If middle element is greater than target, search left side of the list. Set the right index to be at the middle – 1.
6. Iterate until match is found or left index is greater than right index.

Two Types of Approach: Recursive and Iterative

Recursive Approach:

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length -1;

        return binarySearch(nums, target, left, right);

    }

    public int binarySearch(int[] nums, int target, int left, int right){
        int middle = (right + left) / 2;

        if(right < left){ 
            return -1;
        }

        if(target == nums[middle]){ 
            return middle;
        }

        if(target < nums[middle]){
            return binarySearch(nums, target, left, middle - 1);
        } else {
            return binarySearch(nums, target, middle + 1, right);
        }
    }
}

Enter fullscreen mode Exit fullscreen mode

Iterative Approach:

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length -1;

        while (right >= left){
            int middle = (right + left) / 2;
            if(target == nums[middle]){ 
                return middle;
            }
            if(target < nums[middle]){
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        return -1; 
    }
}

Enter fullscreen mode Exit fullscreen mode

原文链接：Binary Search Technique