在预排序数组中找到给定值的最低索引

本文介绍了在预排序数组中找到给定值的最低索引的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

嘿，我在采访中有这个问题，想知道什么是解决这个问题的最佳方法。所以说给你一个已经排序的数组，你想找到某个值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 而不是数组中的任何一个：

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