tìm chỉ số thấp nhất của một giá trị đã cho trong một mảng được phân loại

Question

Hey Tôi đã có câu hỏi này trong một cuộc phỏng vấn và đang tự hỏi cách tốt nhất để giải quyết nó là gì. Vì vậy, nói rằng bạn đang đưa ra một mảng đã được sắp xếp và bạn muốn tìm chỉ mục thấp nhất của một số giá trị x.

Đây là một python/pseudocode của những gì tôi đã đưa ra, tôi chỉ tự hỏi nếu có một cách tốt hơn để đi về nó?

def findLowestIndex(arr, x): 
    index = binarySearch(0, len(arr), x) 
    if index != -1: 
     while index > 0: 
      if arr[index] == arr[index-1]: 
       index -= 1 
      else: 
       break 
    return index 

Cảm ơn!

Answer 1

phương pháp của bạn cần có thời gian tuyến tính trong trường hợp xấu nhất, đó là khi đếm x s trong mảng là O (n).

Một O (lg n) giải pháp có thể thu được bằng cách thay đổi tìm kiếm nhị phân thân để tìm x đầu tiên trong mảng thay vì chỉ cần bất kỳ một trong số họ:

def binary_search(x, a): 
    lo = 0 
    hi = len(a) 

    while lo < hi: 
     mid = (lo + hi) // 2 

     if a[mid] < x: 
      lo = mid + 1 
     elif a[mid] > x: 
      hi = mid 
     elif mid > 0 and a[mid-1] == x: 
      hi = mid 
     else: 
      return mid 

    return -1 

Answer 2

import bisect 
l = [1,2,3,4,4,4,4,4,5,5,5,5,5,6,6,7,7,7,8,8] 
bisect.bisect_left(l, 4) 

EDIT: Tôi chỉ bỏ lỡ một điều. các bisect sẽ cung cấp cho bạn một điểm chèn. vì vậy nếu x không có trong danh sách, bạn sẽ vẫn có chỉ mục kết quả. Vì vậy, bạn cần phải kiểm tra xem x có trong danh sách đầu tiên:

if x in l: 
    .... 

nhưng đối với câu hỏi phỏng vấn, họ có thể muốn xem cách bạn đưa ra các thuật toán thay vì sử dụng thư viện ...

Answer 3

tôi 'd đặt cược tiền tốt mà bình luận của gddc là câu trả lời nhanh nhất cho python. Nếu không, thuật toán chung của bạn là chính xác, ngoại trừ thực tế là trong một số trường hợp, bạn có thể đánh bại hành vi O (log n) của tìm kiếm nhị phân. Cụ thể, trong trường hợp số nguyên tốt nhất các hành vi hợp tồi tệ nhất bạn có thể nhận được là O (sqrt (log n)): https://stackoverflow.com/questions/4057258/faster-than-binary-search-for-ordered-list

Answer 4

Nếu yếu tố này là số nguyên - hoặc liệt kê, bạn có thể làm nhanh hơn một chút:

Lưu ý rằng trong tìm kiếm nhị phân [thuật toán, không phải hàm python], nếu phần tử không tồn tại - bạn có thể tìm phần tử nhỏ nhất lớn hơn sau đó chỉ mục.

1. tìm kiếm đầu tiên x - và nhận chỉ mục, để cho nó là i.
2. tiếp theo, tìm kiếm x-1. Nếu nó không có trong danh sách, tìm kiếm nhị phân có thể tìm thấy bạn chỉ mục đầu tiên nếu x.
3. Nếu nó có trong danh sách, chúng ta hãy chỉ số tìm thấy được j:
   • Thực hiện tìm kiếm nhị phân trên sublist j-i, và tìm kiếm một yếu tố mà list[k] < list[k+1]

Đối với không được liệt kê giá trị, nó cũng có thể được thực hiện bằng cùng một ý tưởng giảm phạm vi trong khi list[k] < list[k+1] and list[k+1] == x nhưng tôi thấy nó đơn giản hơn để hiểu đầu tiên nó được thực hiện như thế nào cho số nguyên và sau đó áp dụng nó cho giải pháp chung.

Lưu ý rằng giải pháp này là O(logn), trong khi các giải pháp tầm thường bạn đề xuất là O(n), trong danh sách với rất nhiều giá trị nhân bản, vì bước lặp sau khi tìm kiếm nhị phân.

Answer 5

Nếu x không nằm trong số X sao cho f(x) = v thì câu trả lời là không đáng kể: Tìm kiếm nhị phân để tìm ra điều đó.

Nếu có một x sao cho f(x) = v thì câu trả lời cũng không quan trọng: Tìm kiếm nhị phân để tìm ra điều đó.

Vấn đề chỉ thú vị nếu có nhiều x 's như vậy mà f(x) = v. Nếu có một số hằng số x thì thuật toán tìm kiếm nhị phân là tối ưu. Chỉ tìm kiếm nhị phân và kiểm tra tuần tự thấp hơn.

Điều gì xảy ra nếu, có rất nhiều trong số này là x? Một tìm kiếm tuần tự như thế rõ ràng là không tối ưu. Trên thực tế, nếu có c * |X|x thì điều này sẽ chạy trong O(|X|).

Thay vì những gì có thể được thực hiện là khởi lbound-0 và tìm kiếm nhị phân cho đến khi bạn tìm thấy nguyên tố này, tại i, nơi mỗi khi bạn đi đúng, cập nhật lbound đến giữa vừa được sử dụng. Sau đó, tìm kiếm nhị phân từ [lbound, i - 1]. Thực hiện việc này cho đến i == lbound hoặc bạn không tìm thấy phần tử. Nếu trường hợp cũ xảy ra, chỉ mục mong muốn là 0. Nếu sau này xảy ra, chỉ mục mong muốn là sử dụng trước đó i. Trường hợp xấu nhất là chỉ mục mong muốn là 0.

Điều thú vị là điều này vẫn chạy trong thời gian log(|X|), tôi nghĩ vậy.

Answer 6

Sửa đổi tìm kiếm nhị phân để tìm bất kỳ lần xuất hiện nào của x lần đầu tiên.

Answer 7

deferred detection of equality approach in binary search cung cấp chỉ mục nhỏ nhất, giảm chi nhánh bình đẳng.

def binary_search(low, high, target, array): 
    while low < high: 
     mid = low + (high - low)/2 
     if a[mid] < target: 
      low = mid + 1 
     else: 
      high = mid 

    if (array[low] == target) return low 
    else return -1