This week I learned about the basic search algorithm: Binary Search. When doing the search, it is easy to just iterate every possible element of the list. Binary search done it differently, it divide the list into two halfs.

The main characteristic of a problem that can be solved using binary search is that the array must be sorted. Then, we utilize these variables: left, right and mid.

func searchInt(arr []int, target int) int {
	left := 0
	right := len(arr) - 1

	for left <= right { // use less than equal to check the latest element
		// mid := (right + left) / 2 // becareful with overflow where the value of right + left > maxInt
		mid := left + (right-left)/2 // the alternative to deal with overflow
		if arr[mid] == target {
			return mid
		}

		if arr[mid] < target {
			left = mid + 1
		} else {
			right = mid
		}
	}

	return -1
}