【Day31】[演算法]-二分搜寻法Binary Search

二分搜寻法(Binary Search )，在执行前有一项必须条件，资料列需要是已排序好的状态，因此若资料庞大且未排序，需要先搭配使用前面几天介绍的排序法，再来执行二分搜寻法。

原理是在已排序好的资料列中找出中间值，再将搜寻的目标值与中间值作比较，如果目标值小於中间值，则往左边资料列寻找，如果目标值大於中间值，则往右边资料列寻找，藉此判断目标值在资料列左边或是右边，每一回都透过选择中间值来比较来缩小一半搜寻范围，再重复前面步骤，直到搜寻到或确定不存在为止。

下面利用10 15 25 40 45 55 60 80 90搜寻55为例。

JavaScript

let data=[10,15,25,40,45,55,60,80,90];
let target=55;

function binarySearch(arr, target){
  let start = 0;
  let end = arr.length - 1;
  let mid;
  
  while(start <= end){
    mid = Math.floor( (start + end ) / 2)
    if(target < arr[mid]){
      end = mid - 1;
    }else if(target > arr[mid]){
      start = mid + 1
    }else{
      return "有搜寻结果: 在第" + (mid+1) + "项";
    }
  }
  return "无搜寻结果";
}

console.log(binarySearch(data,target));//"有搜寻结果: 在第6项"

Python

#Linear Search

data = [10,15,25,40,45,55,60,80,90]
target = 55
def binarySearch(arr, target):
    start = 0
    end = len(arr)-1
    while start <= end:
        mid = int((start + end) / 2)
        if target == arr[mid]:
            return "有搜寻结果: 在第" + str(mid+1) + "项"
        elif target > arr[mid]:
            start = mid + 1
        else:
            end = mid - 1
    return "无搜寻结果"

print(binarySearch(data,target))#有搜寻结果: 在第6项