cách nhanh nhất để xác định xem một phần tử có nằm trong một mảng được sắp xếp hay không

Question

Tôi có một mảng ints được sắp xếp có giá trị từ 1.000 trở lên (có thể lên tới 5000+). Tôi cần phải viết một hàm nhận int và trả về một bool dựa trên phần tử nằm trong mảng. Tôi biết tôi có thể viết một vòng lặp for với một break, tôi biết tôi có thể sử dụng jquery .InArray.

Cách tốt nhất để thực hiện điều này là gì, BIẾT rằng mảng được sắp xếp.

Cảm ơn.

Answer 1

Biết rằng mảng được sắp xếp tìm kiếm nhị phân sẽ là cách tiếp cận tốt nhất.

Answer 2

Nếu sắp xếp của mảng, sau đó sắp xếp câu trả lời - hãy sử dụng mã nhị phân.

Answer 3

Tôi nghĩ bạn muốn sử dụng một thói quen tìm kiếm nhị phân. Một thói quen tìm kiếm nhị phân là trong khi tìm kiếm tuyến tính trung bình là .

Có nhiều biến thể để chọn biểu mẫu. Dưới đây là một tôi tìm thấy trong this article:

function binarySearch(items, value){ 

    var startIndex = 0, 
     stopIndex = items.length - 1, 
     middle  = Math.floor((stopIndex + startIndex)/2); 

    while(items[middle] != value && startIndex < stopIndex){ 

     //adjust search area 
     if (value < items[middle]){ 
      stopIndex = middle - 1; 
     } else if (value > items[middle]){ 
      startIndex = middle + 1; 
     } 

     //recalculate middle 
     middle = Math.floor((stopIndex + startIndex)/2); 
    } 

    //make sure it's the right value 
    return (items[middle] != value) ? -1 : middle; 
} 

Hoặc tìm phiên bản này đơn giản hơn từ this article mà có một chức năng tìm kiếm nhị phân trong một zillion ngôn ngữ khác nhau.

function binary_search_iterative(a, value) { 
    var lo = 0, hi = a.length - 1, mid; 
    while (lo <= hi) { 
     mid = Math.floor((lo+hi)/2); 
     if (a[mid] > value) 
      hi = mid - 1; 
     else if (a[mid] < value) 
      lo = mid + 1; 
     else 
      return mid; 
    } 
    return null; 
} 

Ngoài ra còn có tìm kiếm nhị phân trong đóng cửa của Google với mã here.

Và mô tả tốt về cách thuật toán tìm kiếm nhị phân hoạt động trên Wikipedia.

Answer 4

Nhiều ngôn ngữ đã được triển khai thực hiện ví dụ trong java, bạn có thể sử dụng phương thức CollectionsCollections.binarySearch (List> list, T key) và tôi chắc chắn C# cũng có một số phương thức BinarySearch.

Answer 5

Nếu thực hiện tra cứu nhiều lần, hãy di chuyển đến đối tượng giống bản đồ.

var fastLookup = {}; 
 
mySortedArray.forEach(function(i){fastLookup[i]=true)}); 
 

 
//Each time: 
 
    if (fastLookup[key]===true){ //do thing 
 
    }