3.8 Binary Search

1. Binary Search

In a sorted array, compare the middle value with the target value.

• target = middle: return the position of middle
• target < middle: continue searching in the left half of the array
• target > middle: continue searching in the right half of the array

2. Implementation

2.1. Java

public class BinarySearch
{
    public static int binarySearch(int[] a, int key)
    {
        int low = 0;
        int high = a.length - 1;

        while (low <= high)
        {
            int mid = (low + high) >>> 1;
            int midVal = a[mid];

            if (midVal < key)// key is larger than the middle value, continue searching on the right
                low = mid + 1;
            else if (midVal > key)// key is smaller than the middle value, continue searching on the left
                high = mid - 1;
            else
                return mid; // key found
        }
        return -1;  // key not found.
    }
}

2.2. Golang

// Non-recursive: find the index where value == target
func BinarySearch(data []model.Comparable, target model.Comparable) int {
	left := 0
	right := len(data) - 1
	for left <= right {
		// left+right may overflow
		//mid := (left + right) / 2
		mid := left + (right-left)/2
		midValue := data[mid]
		// target is on the left side of the array
		if midValue.CompareTo(target) > 0 {
			right = mid - 1
		// target is on the right side of the array
		} else if midValue.CompareTo(target) < 0 {
			left = mid + 1
		} else {
			return mid
		}
	}
	return -1
}

// Recursive: find the index where value == target
func BinarySearch2(data []model.Comparable, target model.Comparable) int {
	return binarySearch2(data, 0, len(data)-1, target)
}

func binarySearch2(data []model.Comparable, left int, right int, target model.Comparable) int {
	if left > right {
		return -1
	}

	mid := left + (right-left)/2
	midValue := data[mid]

	// target is on the left side of the array
	if midValue.CompareTo(target) > 0 {
		return binarySearch2(data, left, mid-1, target)
	}
	// target is on the right side of the array
	if midValue.CompareTo(target) < 0 {
		return binarySearch2(data, mid+1, right, target)
	}

	return mid
}

2.2.1. Test

func TestBinarySearch(t *testing.T) {
	e1 := model.NewElement(1)
	e2 := model.NewElement(2)
	e3 := model.NewElement(3)
	data := []model.Comparable{e2, e1, e3}
	fmt.Println(data)

	sort.InsertionSort2(data)
	fmt.Println(data)

	fmt.Println(BinarySearch2(data, e2))
}

3. Binary Search Variants

3.1. upper

// Find the smallest value greater than target
func UpperBinarySearch(data []model.Comparable, target model.Comparable) int {
	left := 0
	// All values may be smaller than target, so initialize right to the array length to indicate not found
	right := len(data)
	for left < right {
		mid := left + (right-left)/2
		midValue := data[mid]
		// middle value <= target, so all values on the left are <= target; search on the right
		if midValue.CompareTo(target) <= 0 {
			left = mid + 1
		} else {
			right = mid
		}
	}
	return left
}

3.1.1. Test

func TestUpperBinarySearch(t *testing.T) {
	e1 := model.NewElement(1)
	e2 := model.NewElement(2)
	e3 := model.NewElement(3)
	data := []model.Comparable{e2, e1, e3}
	fmt.Println(data)

	sort.InsertionSort2(data)
	fmt.Println(data)

	fmt.Println(UpperBinarySearch(data, e1))
	fmt.Println(UpperBinarySearch(data, e3))

}

3.2. ceil

• For example: 1 1 3 3 5 5 7 7
  • Search for 5: if the element exists in the array, return the largest index, which is index 5
  • Search for 6: if the element does not exist in the array, return upper, which is index 6
• It is implemented based on upper

// Find the smallest value greater than target (including target)
func UpperBinarySearch(data []model.Comparable, target model.Comparable) int {
	left := 0
	// All values may be smaller than target, so initialize right to the array length to indicate not found
	right := len(data)
	for left < right {
		mid := left + (right-left)/2
		midValue := data[mid]
		// middle value <= target, so all values on the left are <= target; search on the right
		if midValue.CompareTo(target) <= 0 {
			left = mid + 1
		} else {
			right = mid
		}
	}
	return left
}

// If a value > target exists, return the index of the smallest value > target
// If a value == target exists, return the largest index equal to target (preferred)
func CeilBinarySearch(data []model.Comparable, target model.Comparable) int {
	upper := UpperBinarySearch(data, target)
	// After finding upper, check whether the position to its left equals target; if so, return that index
	if upper-1 >= 0 && data[upper-1].CompareTo(target) == 0 {
		return upper - 1
	}
	return upper
}

3.2.1. Test

func TestCeilBinarySearch(t *testing.T) {
	e1 := model.NewElement(1)
	e2 := model.NewElement(2)
	e3 := model.NewElement(3)
	data := []model.Comparable{e2, e1, e3}
	fmt.Println(data)

	sort.InsertionSort2(data)
	fmt.Println(data)

	fmt.Println(CeilBinarySearch(data, e1))
}

3.3. lower

// Find the index of the largest value smaller than target
func LowerBinarySearch(data []model.Comparable, target model.Comparable) int {
	// All values may be greater than target, so initialize left to -1 to indicate not found
	left := -1
	right := len(data) - 1
	for left < right {
		mid := left + (right-left + 1)/2
		midValue := data[mid]
		// middle value < target, so all values on the left are < target; search on the right
		if midValue.CompareTo(target) < 0 {
			left = mid
		} else {
			right = mid - 1
		}
	}

	return left
}

3.3.1. Test

func TestLowerBinarySearch(t *testing.T) {
	e0 := model.NewElement(0)

	e1 := model.NewElement(1)
	e2 := model.NewElement(2)
	e3 := model.NewElement(3)
	data := []model.Comparable{e2, e1, e3}
	fmt.Println(data)

	sort.InsertionSort2(data)
	fmt.Println(data)

	fmt.Println(LowerBinarySearch(data, e3))
	fmt.Println(LowerBinarySearch(data, e0))

}

4. Binary Search Problem-Solving Patterns

4.1. Basic Principles

• Reduce the search range every time
• Each reduction must not exclude a potential answer

4.2. Templates

4.2.1. Find an Exact Value

• Loop condition: l<=r
• Reduce search space: l=mid+1, r=mid-1

4.2.2. Find a Fuzzy Boundary Value

• Loop condition: l<r
• Reduce search space: l=mid, r=mid-1 or l=mid+1, r=mid

4.2.3. General-Purpose Form

• Loop condition: l<r-1
• Reduce search space: l=mid, r=mid
•