在预排序数组中找到给定值的最低索引 [英] find lowest index of a given value in a presorted array

问题描述

嘿，我在采访中有这个问题，想知道什么是解决这个问题的最佳方法。所以说给你一个已经排序的数组，你想找到某个值x的最低索引。

Hey I had this question in an interview and was wondering what was the best way to solve it. So say you are given an array that is already sorted and you want to find the lowest index of some value x.

这是我想出的python / pseudocode与，我只是想知道是否还有更好的方法？

Here is a python/pseudocode of what I came up with, I am just wondering if there is a better way to go about it?

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

谢谢！

推荐答案

在最坏的情况下，即数组中 x s的计数为O（ n ）时，您的方法会花费线性时间。

Your method takes linear time in the worst case, which is when the count of xs in the array is O(n).

可以通过更改二进制搜索本身以找到第一个 x n ）解决方案c $ c>而不是数组中的任何一个：

An O(lg n) solution can be obtained by changing the binary search itself to find the first x in the array instead of just any one of them:

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

这篇关于在预排序数组中找到给定值的最低索引的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！