二分查找
一个从小到大排列的数组 li, 设定一个值 val, 找出这个值在数组中的位置, 如果没有找到, 返回 -1;
思路:
-
- 设定两个下标值,
- left: 数组的第一个值: 0,
- right: 数组的最后一个值: 数组的长度-1
-
- 找到数组中间位置mid, 将中间位置的值, 与待查找的值相比较
- mid 等于 left 加 right, 除以2 然后取整
- 如果中间的值,与待查找的值相同, 则mid就是目标值
-
- 如果中间位置的值 > 待查找的值, 说明中间位置往后的值, 都不符合要求
- 此时right = mid - 1
-
- 如果中间位置的值 < 待查找的值, 说明中间位置往前的值, 都不符合要求
- 此时 left = mid + 1
- 循环2-5, 如果出现 left > right 的情况出现, 则说明没有找到对应的值
代码实现---python
def binary_search(li, val):
left = 0
right = len(li) - 1
while left <= right:
mid = (left + right) // 2
if li[mid] == val:
return mid
elif li[mid] > val:
right = mid - 1
else:
left = mid + 1
else:
return -1
代码实现---js
function binary_search(li, val){
let left = 0;
let right = li.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) /2)
if (li[mid] === val) {
return mid
} else if( li[mid] > val) {
right = mid - 1
} else {
left = mid + 1
}
}
return -1
}
