Binary Search

Binary search is an efficient way of searching for elements within a sorted array. Typically we are given an array, and a target element to search for.

The idea behind binary search is similar to how we would search for a word in a dictionary. We would open the dictionary in the middle and determine if the word we are looking for is in the left or right half. We would then repeat this process until we find the word or determine that it doesn't exist in the dictionary.

Similarly, binary search divides a given array by the middle index, called mid and compares the value at mid to the target value. If the target is greater than the mid value, we will search the right half of the array. If the target is less than the mid value, we will search the left half of the array.

In interviews and algorithmic problems, there are two common variations of binary search problems:

1. Search Array - a sorted array, and a target is given and the task is to determine if the target is found in the array.
2. Search Range - a range of numbers is given rather than an array, without a specific target.

package main
import "fmt"

func binarySearch(arr []int, target int) int {
	L, R := 0, len(arr)-1
	var mid int

	for L <= R {
		mid = (L + R) / 2
		if target > arr[mid] {
			L = mid + 1
		} else if target < arr[mid] {
			R = mid - 1
		} else {
			return mid
		}
	}
	return -1
}

func main() {
	fmt.Println(binarySearch([]int{1, 3, 3, 4, 5, 6, 7, 8}, 5))
}

Related:
mul-dim-bin-search