hakk

Binary Search

Binary Search is a searching algorithm for finding an element’s position, if it exists, in a sorted array.

Implementation

def search(nums, k):

	right = len(nums)
	left = 0

	while left <= right:

		mid = (left + right) // 2
		
		if nums[mid] == k:
			return mid
		elif nums[mid] > k:
			right = mid - 1
		else:
			left = mid + 1

	return -1

func search(nums []int, key int) int {
	left := 0;
	right := len(nums)
	var mid int

	for left <= right {
		mid = left + (right - left) / 2
		
		if nums[mid] == key {
			return mid
		}

		if nums[mid] < key {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return -1
}

function search(array, key) {
    let left = 0;
    let right = array.length - 1;

    while (left <= right) {
        mid = Math.round( (left + right) / 2 );
        
        if (array[mid] === key) {
            return mid;
        } else if (array[mid] > key) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return -1;
}

int binarySearch(vector nums, int x) {
	int left = 0;
	int right = nums.size();

	while (left <= right) {
		int mid = left + (right - left) / 2;

		if (nums[mid] == x)
			return mid;
		if (nums[mid] < x)
			left = mid + 1;
		else
			right = mid - 1;
  	}
  	return -1;
}

public class BinarySearch {

    public static int search(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (array[mid] == target) {
                return mid;
            } else if (array[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

}

Complexity

Time Complexities

Space Complexity

The space complexity of the binary search is O(1).