iT邦幫忙

2021 iThome 鐵人賽

0
Software Development

資料結構與演算法,使用JavaScript與Python系列 第 31

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

二分搜尋法(Binary Search ),在執行前有一項必須條件,資料列需要是已排序好的狀態,因此若資料龐大且未排序,需要先搭配使用前面幾天介紹的排序法,再來執行二分搜尋法。

原理是在已排序好的資料列中找出中間值,再將搜尋的目標值與中間值作比較,如果目標值小於中間值,則往左邊資料列尋找,如果目標值大於中間值,則往右邊資料列尋找,藉此判斷目標值在資料列左邊或是右邊,每一回都透過選擇中間值來比較來縮小一半搜尋範圍,再重複前面步驟,直到搜尋到或確定不存在為止。


下面利用10 15 25 40 45 55 60 80 90搜尋55為例。
https://ithelp.ithome.com.tw/upload/images/20211012/20121027rqGyJGUz83.jpg


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項

上一篇
【Day30】[演算法]-線性搜尋法Linear Search
下一篇
【Day32】[演算法]-內插搜尋法Interpolation Search
系列文
資料結構與演算法,使用JavaScript與Python35

尚未有邦友留言

立即登入留言