Binary search

The simple binary lookup implemented here (there are no duplicate elements in an ordered array).

// Non-recursive implementation const binarySearch = (arr, target) => {let low = 0, high = arr.length - 1;
	while (low <= high) {
		const mid = parseInt(low + (high - low) / 2);
		if (arr[mid] === target) {
			return mid;
		} else if (arr[mid] > target) {
			high = mid - 1;
		} else{ low = mid + 1; }}return- 1; Const binarySearch = (arr, target) => {return helper(arr, 0, arr.length - 1, target);
}

const helper = (arr, low, high, target) => {
	if (low > high) {
		return - 1;
	}
	const mid = low + ((high - low) >> 1);
	if (arr[mid] === target) {
		return mid;
	} else if (arr[mid] < target) {
		return helper(arr, mid + 1, high, target);
	} else {
		returnhelper(arr, low, mid - 1, target); Var arr1 = [1, 3, 5, 6, 8, 10]; binarySearch(arr1, 3); //1 binarySearch(arr1, 10); //5 binarySearch(arr1, 7); / / 1Copy the code

Find the element whose first value is equal to the given value (duplicate elements exist)

const binarySearch1 = (arr, target) => {
	let low = 0, high = arr.length - 1;
	while (low <= high) {
		const mid = low + ((high - low) >> 1);
		if (arr[mid] > target) {
			high = mid - 1;
		} else if (arr[mid] < target) {
			low = mid + 1;
		} else {
			if((mid === 0) || arr[mid - 1] ! = target) {return mid;
			} else{ high = mid - 1; }}}return- 1; } var arr = [1,3,5,6,6,6,8]; binarySearch1(arr,6); / / 3Copy the code

Find the element whose last value is equal to the given value (duplicate elements exist)

const binarySearch2 = (arr, target) => {
	let low = 0, high = arr.length - 1;
	while (low <= high) {
		const mid = low + ((high - low) >> 1);
		if (arr[mid] > target) {
			high = mid - 1;
		} else if (arr[mid] < target) {
			low = mid + 1;
		} else {
			if((mid === arr.length - 1) || arr[mid + 1] ! = target) {return mid;
			} else{ low = mid + 1; }}}return- 1; } var arr = [1,3,5,6,6,6,8]; binarySearch2(arr,6); / / 5Copy the code

Finds the first element greater than or equal to the given value

const binarySearch3 = (arr, target) => {
	let low = 0, high = arr.length - 1;
	while (low <= high) {
		const mid = low + ((high - low) >> 1);
		if (arr[mid] >= target) {
			if ((mid === 0) || arr[mid - 1] < target) {
				return mid;
			} else{ high = mid - 1; }}else{ low = mid + 1; }}return- 1; } var arr = [3,4,6,7,10]; binarySearch3(arr,5); / / 2Copy the code

Finds the last element that is less than or equal to the given value

const binarySearch4 = (arr, target) => {
	let low = 0, high = arr.length - 1;
	while (low <= high) {
		const mid = low + ((high - low) >> 1);
		if (arr[mid] > target) {
			high = mid - 1;
		} else {
			if ((mid === arr.length - 1) || (arr[mid + 1] > target)) {
				return mid;
			} else{ low = mid + 1; }}}return- 1; } var arr = [3,4,6,7,10]; binarySearch4(arr,9); / / 3Copy the code

LeetCode related topic

1. Binary search leetcode-cn.com/tag/binary-…

29. Divide the two numbers leetcode-cn.com/problems/di…

33. Search rotation sort array leetcode-cn.com/problems/se…

34. Find the first and last positions of elements in the sorted array leetcode-cn.com/problems/fi…

35. Search for insert location leetcode-cn.com/problems/se…

(x, n) leetcode-cn.com/problems/po 50. The Pow…

69. The square root of x leetcode-cn.com/problems/sq…