ThinkerQAQ

NOTE

3.8 二分查找

1. 二分查找 在已排序的数组中，取中间值【middle】跟查找值【target】比较 - target = middle，那么就返回middle的位置 - target < middle的话，那么在数组左半部分继续查找 - target middle的话，那么在数组右半部分继续查找 2. 实现 2

Data Structures & Algorithms创建于 更新于 historical

这是历史学习笔记，可能存在过时或不完整的理解。

1. 二分查找

在已排序的数组中，取中间值【middle】跟查找值【target】比较

  • target = middle，那么就返回middle的位置
  • target < middle的话，那么在数组左半部分继续查找
  • target > middle的话，那么在数组右半部分继续查找

2. 实现

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比中间值大，那么在右边继续找
                low = mid + 1;
            else if (midVal > key)//key比中间值小，那么在左边继续找
                high = mid - 1;
            else
                return mid; // key found
        }
        return -1;  // key not found.
    }
}

2.2. Golang

//非递归 寻找==target的索引
func BinarySearch(data []model.Comparable, target model.Comparable) int {
	left := 0
	right := len(data) - 1
	for left <= right {
		//left+right可能会overflow
		//mid := (left + right) / 2
		mid := left + (right-left)/2
		midValue := data[mid]
		// target在数组的左边
		if midValue.CompareTo(target) > 0 {
			right = mid - 1
		// target在数组的右边
		} else if midValue.CompareTo(target) < 0 {
			left = mid + 1
		} else {
			return mid
		}
	}
	return -1
}

//递归 寻找==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) / 2
	midValue := data[mid]

	// target在数组的左边
	if midValue.CompareTo(target) > 0 {
		return binarySearch2(data, 0, mid-1, target)
	}
	// target在数组的右边
	if midValue.CompareTo(target) < 0 {
		return binarySearch2(data, mid+1, right, target)
	}

	return mid
}

2.2.1. 测试

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. 二分查找变种

3.1. upper

// 寻找比target大的最小值
func UpperBinarySearch(data []model.Comparable, target model.Comparable) int {
	left := 0
	// 有可能所有值都比target小，所以right初始化为数组长度表示这个值不存在
	right := len(data)
	for left < right {
		mid := left + (right-left)/2
		midValue := data[mid]
		//中间值<=目标值，那么左边的所有值都是<=目标值，应该在右边找
		if midValue.CompareTo(target) <= 0 {
			left = mid + 1
		} else {
			right = mid
		}
	}
	return left
}

3.1.1. 测试

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

  • 比如1 1 3 3 5 5 7 7
    • 查找5：如果数组中存在元素,返回最大索引，即index 5
    • 查找6：如果数组中不存在元素,返回 upper，即index 6
  • 其实就是基于upper实现的
// 寻找比target大的最小值（包含target）
func UpperBinarySearch(data []model.Comparable, target model.Comparable) int {
	left := 0
	// 有可能所有值都比target小，所以right初始化为数组长度表示这个值不存在
	right := len(data)
	for left < right {
		mid := left + (right-left)/2
		midValue := data[mid]
		//中间值<=目标值，那么左边的所有值都是<=目标值，应该在右边找
		if midValue.CompareTo(target) <= 0 {
			left = mid + 1
		} else {
			right = mid
		}
	}
	return left
}

// 如果有 > target的数, 那么返回>target的最小值的索引
// 如果有 == target的数，返回== target的最大索引（优先）
func CeilBinarySearch(data []model.Comparable, target model.Comparable) int {
	upper := UpperBinarySearch(data, target)
	//upper找到后，看一下左边那个位置是否==target，是的话返回那个值的索引
	if upper-1 >= 0 && data[upper-1].CompareTo(target) == 0 {
		return upper - 1
	}
	return upper
}

3.2.1. 测试

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

// 寻找比target小的最大值的索引
func LowerBinarySearch(data []model.Comparable, target model.Comparable) int {
	//可能数组中所有数都比target大，所以初始化left为-1表示不存在
	left := -1
	right := len(data) - 1
	for left < right {
		mid := left + (right-left + 1)/2
		midValue := data[mid]
		//中间值<目标值，那么左边的所有值都是<目标值，应该在右边找
		if midValue.CompareTo(target) < 0 {
			left = mid
		} else {
			right = mid - 1
		}
	}

	return left
}

3.3.1. 测试

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. 二分查找解题套路

4.1. 基本原则

  • 每次都要缩减搜索区域
  • 每次缩减不能排除潜在答案

4.2. 模板

4.2.1. 找一个准确值

  • 循环条件：l<=r
  • 缩减搜索空间：l=mid+1, r=mid-1

4.2.2. 找一个模糊值

  • 循环条件：l<r
  • 缩减搜索空间：l=mid, r=mid-1或者l=mid+1, r=mid

4.2.3. 万用型

  • 循环条件：l<r-1
  • 缩减搜索空间：l=mid, r=mid