算法：二分查找

一、简介

二分查找算法是查找算法中的常见的算法，基本的思想是设置开始索引和结束索引，选取中间点，当中间点索引的取值小于目标值的时候，说明目标值在查找数组的后半段，当中间点索引的值大于目标值的时候，说明目标值在数组的前半段，依次类推，最后找到目标值。

二、算法思想

1.算法条件：查找数组有序

2.算法思路：

初始化左边界i = 0,右边界j = len(nums) - 1
计算中间点 med = i + (j - i) / 2 #思考一：大家可以想一下，这里为什么要这样写
若：nums[med] < target , 则target在闭区间[med+1,j]中，执行i = med + 1;
若：nums[med] > target,则target在闭区间[i,med - 1]中，执行j = med - 1
若：nums[med] = target，返回med索引
结束

我们大概梳理一下二分查找的算法思路：

找到中间值
利用有序数组的特性，根据中间值比较条件，进行区间的切割
若找到目标值就返回目标值的索引，若没有找到目标值，按照要求进行返回

三、算法增强

我最近在刷leetcode，我从中找了几个有关二分查找的题，使用go语言进行解题分析。

题目1：常规题

描述：在一个有序的数组中，查找一个值，返回该值的索引，若没有目标值，返回-1，若由重复值，返回其中任意一个值的索引

例子：

输入: nums = [5,7,7,8,8,10], target = 7
输出: 1 或 2

这是一道经典的二分查找题，我想这道题的思路大家都会，我就直接上go的代码了：

func BinarySearch(srcnums []int,targetNums int) int {
	var l,r int = 0,len(srcnums)-1
	for l<=r {
		meddle := l + (r -l)/2
		if srcnums[meddle] == targetNums{
			return meddle
		}else if srcnums[meddle] < targetNums{
			l = meddle +1
		}else{
			r = meddle-1
		}
	}
	return -1	
}

2.题目二：增强题

统计一个数字在排序数组中出现的次数。

例子：
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

题目解析：

方法一：这个题我们可以直接用暴力解法，遍历一遍数组，得出目标值出现的次数，这个肯定不是我今天要分享的解法。

方法二：上面的解法没有充分利用数组的有序的特点，一想到数组有序，我就想到二分，二分可以利用数组有序的特性，那么我们怎么往二分的框架上靠那？我们注意到，利用有序的特性，我们可以先找到第一个出现的索引firstT，我们在找到最后一个出现的索引lastT，然后进行相减lastT - firstT,那么我们怎么能快速的找到两个索引那？这个时候我们就能使用二分查找了，我们在闭区间[i,j]上面找，中间值med = (i+j)/2，当中间值等于target时，我们判断一下他左边的一个元素是否为target，若他左边的元素为target时，我们就找到了firstT，若左边的一个元素也是target时，说明我们要找的firstT在数组的前半段，则j = med - 1,当med的值> target时，也说明firstT的值在数组的前半段，当med值小于target值的时候，则说明firstT在数组的后半段，这样我们就使用二分法找到了firstT，lastT同理也能找到

search.go代码如下：

func search(nums []int, target int) int {
	// return countN(nums, target)
	if len(nums) == 0 {
		return 0
	}
	firstK := GetFirstK(nums, target)
	lastK := GetLastK(nums, target)
	if firstK != -1 && lastK != -1 {
		return lastK - firstK + 1
	}
	return 0
}

func countN(nums []int, target int) int {
	if len(nums) == 0 {
		return 0
	}
	r := 0
	for i := 0; i < len(nums); i++ {
		if nums[i] == target {
			r++
		}
	}
	return r
}

func GetFirstK(nums []int, target int) int {
	if len(nums) == 0 {
		return -1
	}
	start, end := 0, len(nums)-1
	rIndex := -1
	if nums[0] == target {
		return 0
	}
	for start <= end {
		mid := start + (end-start)/2
		if nums[mid] == target && nums[mid-1] != target {
			rIndex = mid
			break
		} else if nums[mid] >= target {
			end = mid - 1
		} else if nums[mid] < target {
			start = mid + 1
		}

	}

	return rIndex
}

func GetLastK(nums []int, target int) int {
	if len(nums) == 0 {
		return -1
	}
	start, end := 0, len(nums)-1
	rIndex := -1
	if nums[len(nums)-1] == target {
		rIndex = len(nums) - 1
		return rIndex
	}
	for start <= end {
		mid := start + (end-start)/2
		if nums[mid] == target && nums[mid+1] != target {
			rIndex = mid
			break
		} else if nums[mid] <= target {
			start = mid + 1
		} else if nums[mid] > target {
			end = mid - 1
		}
	}
	return rIndex
}

search_test.go测试代码如下：

import "testing"

func TestSearch(t *testing.T) {
	type test struct {
		input  []int
		target int
		want   int
	}

	testcase := map[string]test{
		"exist":         test{input: []int{5, 7, 7, 8, 8, 10}, target: 8, want: 2},
		"notexist":      test{input: []int{5, 7, 7, 8, 8, 10}, target: 2, want: 0},
		"boardexist":    test{input: []int{5, 7, 7, 8, 8, 10}, target: 5, want: 1},
		"boardendexist": test{input: []int{5, 7, 7, 8, 8, 10}, target: 10, want: 1},
	}

	for k, v := range testcase {
		t.Run(k, func(t *testing.T) {
			got := search(v.input, v.target)
			if got != v.want {
				t.Errorf("the excepted is %v,the got is %vn", v.want, got)
			}
		})
	}
}

测试的注意事项：

常规测试，数组中存在目标值，数组中不存在目标值
边界测试：firstT在0索引处，lastT在最右索引

这个算法的时间复杂度为o(logn)，对数组使用了两遍的二分查找，

空间复杂度为o(1)

2.题目三：增强题

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

题目解析：

方法一：同样，我们也能够遍历数组，这个数组的特点就是有序，在缺少的数字之前数组元素的下标与数组元素相同，之后的数组中，数组元素的下标都比数组元素小，这样我们遍历一遍的时候就能找到了，但是时间复杂度o(n)

方法二：这道题我们也能利用数组有序的特性进行二分查找缺失的数字，我们在[i,j]闭区间内查找缺失的值，mid = (i+j)/2,当nums[mid] > mid的时候，缺失的值在前半段数组，则j = mid - 1，当nums[mid] = mid 缺失的值在后半段的数组中，则i = mid + 1;这样到最后，i的值处于第一个nums[mid] != mid 的索引处，因此返回i的索引值即为结果。

search.go代码如下：

func missingNumber(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	start, end := 0, len(nums)-1
	if nums[0] != 0 {
		return 0
	}
	if nums[len(nums)-1] == len(nums)-1 {
		return len(nums)
	}
	for start <= end {
		mid := start + (end-start)/2
		if nums[mid] == mid {

			start = mid + 1
		} else if nums[mid] > mid {

			end = mid - 1
		}
	}
	return start
}

search_test.go代码如下：

import "testing"

func TestSearch(t *testing.T) {
	type test struct {
		input []int
		want  int
	}

	testcase := map[string]test{
		"mid":     test{input: []int{0, 1, 2, 3, 4, 5, 7, 8}, want: 6},
		"first":   test{input: []int{1, 2, 3, 4, 5, 6, 7, 8}, want: 0},
		"last":    test{input: []int{0, 1, 2, 3, 4, 5, 6, 7}, want: 8},
		"single":  test{input: []int{0}, want: 1},
		"single1": test{input: []int{1}, want: 0},
	}

	for k, v := range testcase {
		t.Run(k, func(t *testing.T) {
			got := missingNumber(v.input)
			if got != v.want {
				t.Errorf("the excepted is %v,the got is %vn", v.want, got)
			}
		})
	}
}