Introduction of Binary Search

Definition

Binary Search is a efficient search technique in which we keep reducing our search space by dividing the array into 2 halves and select any one half as a new search space.

note

binary search can only be applied to an array that is already sorted in ascending or descending order, or to an array that is monotonically increasing or decreasing

Example

Input: nums = [-1,0,3,5,9,12], target = 5
Output: 3
Explanation: 5 exists in nums and its index is 3

You can try this at:

• https://leetcode.com/problems/binary-search

Approach

1. The initial search space is the entire array, with low set to 0 and high set to n-1, where n is the size of the array.
2. The middle element of the search space is extracted by calculating mid = low + (high - low) / 2. This ensures that the middle element is calculated correctly and avoids potential integer overflow issues.
3. If the middle element is equal to the target value, it means the desired value has been found, so we return the index of the middle element.
4. If the target value is greater than the middle element, we update low to mid + 1 as the desired value must be in the right half of the search space.
5. If the target value is less than the middle element, we update high to mid - 1 as the desired value must be in the left half of the search space.
6. Steps 2 to 5 are repeated until low is less than or equal to high, ensuring that the search space is properly narrowed down.
7. If the target element is not found within the search space, we return -1 to indicate that it was not found

Code

Java

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

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return -1; // not found
    }
}

Cpp

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int low = 0;
        int high = nums.size() - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return -1; // not found
    }
};

Python

class Solution:
    def search(self, nums, target):
        low = 0
        high = len(nums) - 1

        while low <= high:
            mid = low + (high - low) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                low = mid + 1
            else:
                high = mid - 1

        return -1  # not found

Complexity

Time Complexity:

O(log(N))

Space Complexity:

O(1)