Find the minimum setpoint index in a pre-sorted array

Question

Hey, I had this question in an interview, and I was wondering what is 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 of x.

Here is the python / pseudo code of what I came up with, I'm just wondering if there is a better way to do this?

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

Thank!

Answer 1

Your method takes linear time in the worst case, when the counter xin the array is O (n).

The O (log n) solution can be obtained by changing the binary search itself to find the first xin the array, and not just any 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

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: . bisect . , x , . , x :

if x in l:
    ....

, ...

Answer 3

- , :

, [, python], , , , .

• x - , i.
• , x-1. , , x.
• , j:
  • j i , list[k] < list[k+1]

while list[k] < list[k+1] and list[k+1] == x, , , .

, O(logn), , , O(n), , - .

Answer 4

x x, f(x) = v, : , .

x , f(x) = v, : , .

, x , f(x) = v. x, . .

, , x? , , . , c * |X| x, O(|X|).

lbound 0 , i, , , lbound , . [lbound, i - 1]. i == lbound . , 0. , i. - 0.

, log(|X|) , .

Answer 5

, .

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

Answer 6

I would bet good money that gddc comment is the fastest answer for python. Otherwise, your general algorithm is correct, except for the fact that in some cases you can beat the behavior of the binary search O (log n). In particular, in the case of integers, the best worst behavior you can get is O (sqrt (log n)): fooobar.com/questions/1109725 / ...

Answer 7

Modify the binary search to find any x occurrence for the first time.