返回在使用二进制搜索的排序列表中可以多次出现的值的第一次出现的位置。

Question

例如，如果list= [2,3,3,4,5,7,7,9,10]。

我想返回索引1。

在这种情况下，没有目标参数，不像我们通常的二进制搜索方式。

[更新]

这是目前我的代码，它应该返回1，因为多值的第一次出现，即2，在索引1处

代码照片的链接

[更新]

Answer 1

像往常一样进行二进制搜索；但当你到达你搜索的项目时，继续向左搜索。

即

• 设置 min 到第一个索引。max 到最后一个（加一个）。
• 看中间的那个((min+max)/2).
• 如果那里的值比你要搜索的值大，则设置 max 到该索引；否则，该 min 到它（加一）。
• 重复，直到找到一个有你要找的值的索引。
• 到目前为止，这只是常规的二进制搜索。现在存储这个索引；它是你当前的最佳候选者。就像你找到的值比你要找的值大一样（即，设置了 max 到该索引），然后继续搜索。

当你的搜索空间用完时（即。min = max)，你找到的最后一个 "候选者 "是你搜索的值的最低索引。

Answer 2

我现在分享给你的代码片段，这将有助于找到你的答案。

int leftIndex(int arr[], int n, int x)
{
    int l = 0, h = n-1;
    int mid = 0;

    while(l <= h)
    {
        mid = l + (h-l)/2;

        if(arr[mid] == x && (mid == 0 || arr[mid-1] != x))
          return mid;

        else if(arr[mid] >= x)
          h = mid-1;
        else l = mid + 1;
    }
    return -1;
}

你只需要了解这段代码.这是像二进制搜索一样简单的代码.只有一个条件,在那里我们需要修改,所以我们可以得到所需的结果。