二分法查找

二分查找

一个从小到大排列的数组 li, 设定一个值 val, 找出这个值在数组中的位置, 如果没有找到, 返回 -1;

思路:

• 1. 设定两个下标值,
  • left: 数组的第一个值: 0,
  • right: 数组的最后一个值: 数组的长度-1
• 2. 找到数组中间位置mid, 将中间位置的值, 与待查找的值相比较
  • mid 等于 left 加 right, 除以2 然后取整
• 3. 如果中间的值,与待查找的值相同, 则mid就是目标值
• 4. 如果中间位置的值 > 待查找的值, 说明中间位置往后的值, 都不符合要求
  • 此时right = mid - 1
• 5. 如果中间位置的值 < 待查找的值, 说明中间位置往前的值, 都不符合要求
  • 此时 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
}