使用JS 实现二分法查找位置

使用二分法查找数值的位置:

前提是数组必须是有序的数组,

基本原理是:获取数组的中间值,与要查到的值x进行对比,中间值大于x,则继续对比中间值前半部分数组,依次类推

代码如下:

// 生成一个有序数组
let createArr = () => {
	let arr = []
	for(let i = 0; i < 1000; i++){
		arr.push(i)
	}
	return arr
}
let arr = createArr()

// 使用二分法查找一个值在有序数组中的索引位置
let findValueUseTwoSplit = (val, arr) => {
	let start = 0
	let end = arr.length - 1 // 获取最大索引
	while (start <= end) {
		debugger
		let mid = Math.ceil((end+start) / 2) // 向上取整
		console.log(`start:${start},mid:${mid},end:${end}`)
		if (arr[mid] === val) {
			return arr[mid]
		} else if (arr[mid] < val) {
			start = mid
		} else if (arr[mid] > val) {
			end = mid
		} else {
			return -1
		}
	}
}

let res = findValueUseTwoSplit(102,arr)
console.log('最终结果:'+res)

执行结果如图

最后

以上就是专注八宝粥最近收集整理的关于使用JS 实现二分法查找位置的全部内容，更多相关使用JS内容请搜索靠谱客的其他文章。