二分查找和它的变种

二分查找是快速定位一个有序数组的算法，它的优点就是减少对比次数。是一个日常生活中也可以用到的算法思想

优点

• 减少对比次数
• o(logn)

缺点

• 要求查找的数组是有序数组
• 查找数组过小二分查找反而慢

原型

思路

• 取出中间数 (right-left)/2 只能得到第一次的中间数，正确做法是 left+(right-left)/2
• 中间数和给到的数比大小，如果中间数大就把数组的左边拿去对比反之也一样

func bsearch(list[]int, num int,left int, right int )  bool{
	for right >= left  {

		center := left+(right-left)/2

		if list[center] == num {
			return true
		} else if list[center] < num  {
			left = center + 1
		} else {
			right = center -1
		}
	}
   return false
}

##变种

查找第一个值等于给定元素

func bsearch(list[]int, num int,left int, right int) int {

	for right >= left  {

		center :=  left + (right-left) >> 1

		if (list[center] > num) {
			right = center
		} else if list[center] < num{
			left = center
		} else if list[center] == num {

			if (center == 0 || list[center-1] != num){
				return center
			} else {
					right = center-1
			}

		}

	}

	return -1

}

查找最后一个值等于给定的元素

func bsearch2(list[]int, num int,left int, right int) int {
	for right >= left {
		center := left + (right-left) >> 1

		if (list[center] > num) {
			right = center
		} else if list[center] < num {
			left = center
		} else if list[center] == num {
			if (center == 0 || list[center+1] != num) {
				return center
			}
			left = left + 1
		}
	}

	return  -1
}

查找第一个大于等于给定的元素

func bsearch3(list[]int, num int,left int, right int) int {

	for right >= left {

		center := left + (right-left) >> 1

		if list[center] >= num {
			if center == 0 || list[center - 1] < num {
				return center
			}
			right = right-1
		} else if list[center] < num {
			left = center
		}
	}

	return -1
}

查找最后一个小于等于给定的元素

func bsearch4(list[]int, num int,left int, right int) int {

	for right >= left {

		center := left + (right-left) >> 1

		if list[center] > num {
			right = center
		} else if list[center] <= num {

			if center == 0 || list[center + 1] > num {
				return center
			}

			left = center + 1
		}
	}

	return -1
}