12

我有一个数组

Values array: 12 20 32 40 52
              ^  ^  ^  ^  ^
              0  1  2  3  4

我必须在其上执行二进制搜索以找到数字所在范围的索引。例如：

  1. 给定数字 -> 19（它位于索引 0 和 1 之间），返回 0
  2. 给定数字 -> 22（位于索引 1 和 2 之间），返回 1
  3. 给定数字 -> 40（位于索引 3 和 4 之间），返回 3

我以以下方式实现了二进制搜索，这对于案例 1 和 3 是正确的，但如果我们搜索案例 2 或 52、55 32 等则不正确。

#include <iostream>
using namespace std;

int findIndex(int values[], int number, unsigned first, unsigned last)
{
    unsigned midPoint;
    while(first<last)
    {
        unsigned midPoint = (first+last)/2;
        if (number <= values[midPoint])
            last = midPoint -1;
        else if (number > values[midPoint])
            first = midPoint + 1;
    }
    return midPoint;
}


int main()
{
    int a[] = {12, 20, 32, 40, 52};
    unsigned i = findIndex(a, 55, 0, 4);
    cout << i;
}

bool found不允许使用其他变量，例如。

4

10 回答 10

14

C 或 C++ 中的范围通常被指定为直接指向下限，但超过上限。除非您感到极度自虐，否则您可能也希望在搜索中遵守该约定。

假设您要遵循这一点，那么您last = midpoint-1;是不正确的。相反，您希望将 last 设置为您将实际使用的范围末尾之后的一个，所以它应该是last = midpoint;

你也只需要一个比较，而不是两个。在二分搜索中，只要两个边界不相等，您将设置中心点的下限或上限，因此您只需进行一次比较即可确定哪个。

至少按照惯例，在 C++ 中，您使用<而不是<=,>等进行所有比较。上述任何方法都可以工作，但遵循仅使用的约定<可以避免对包含的类型施加额外（不必要的）要求。

尽管大多数面试官可能不在乎，但当你这样做时，也有潜在的溢出midpoint = (left + right)/2;。我通常更喜欢midpoint = left + (right - left)/2;

考虑到这些，代码可能看起来像这样：

template <class T>
T *lower_bound(T *left, T *right, T val) {
    while (left < right) {
        T *middle = left + (right - left) / 2;
        if (*middle < val)
            left = middle + 1;
        else
            right = middle;
    }
    return left;
}

template <class T>
T *upper_bound(T *left, T *right, T val) {
    while (left < right) {
        T *middle = left + (right - left) / 2;
        if (val < *middle)
            right = middle;
        else
            left = middle + 1;
    }
    return left;
}
于 2012-06-07T16:27:26.383 回答
3

为什么不使用标准库函数？

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int main() {
    for (int input = 10; input < 55; input++) {
        cout << input << ": ";

        // Your desire:
        vector<int> v = { 12, 20, 32, 40, 52 };
        if (input < v.front() || input > v.back()) {
            cout << "Not found" << endl;
        } else {
            auto it = upper_bound(v.begin(), v.end(), input);
            cout << it - v.begin() - 1 << endl;
        }
    }
}

注意：一个非常酷的网站 - http://en.cppreference.com/w/cpp/algorithm

于 2013-03-30T22:30:15.603 回答
1

这将在 min(A[i]) <= key <=max(A[i])的条件下工作 

int binary_search(int A[],int key,int left, int right)
{

  while (left <= right) {
        int middle = left + (right - left) / 2;
        if (A[middle] < key)
            left = middle+1;
        else if(A[middle] > key)
            right = middle-1;
        else
            return middle;
    }
    return (left - 1);
}
于 2012-06-10T12:29:59.623 回答
1

对于输入

4

1 3 8 10

4

输出

3（3和8中的最小值）

#include <stdio.h>

int main()
{
   int c, first, last, middle, n, search, array[100];


   scanf("%d",&n);



for (c = 0; c < n; c++)
  scanf("%d",&array[c]);


   scanf("%d", &search);

   first = 0;
   last = n - 1;
   middle = (first+last)/2;

while (first <= last) {

  if (array[middle] < search)
  { 
     first = middle + 1;    }
  else if (array[middle] == search) {

     break;
  }
  else
  {  
     last = middle - 1;
  }

  middle = (first + last)/2;
 }
  printf("%d\n",array[middle]);
   return 0;   
 }
于 2015-10-21T16:34:06.747 回答
0

成功的常规二进制搜索返回键的索引。如果找不到键，它总是停在比我们正在搜索的键大的最低键的索引处。我想以下修改后的二进制搜索算法会起作用。

Given sorted array A
Find a key using binary search and get an index. 
If A[index] == key
    return index;
else 
   while(index > 1 && A[index] == A[index -1]) index = index -1;
   return index;
于 2012-06-07T23:22:23.093 回答
0 
binsrch(array, num, low, high) {
if (num > array[high])
     return high;


while(1) {
     if (low == high-1)
          return low;
     if(low >= high)
          return low-1;        
     mid = (low+high)/2
     if (num < arr[mid])
          high = mid;
     else
          low = mid+1;
    }
}
于 2012-06-08T20:30:08.390 回答
0

这是一个更具体的答案

int findIndex(int values[],int key,int first, int last)
{
    if(values[first]<=key && values[first+1]>=key)// stopping condition
    {
        return first;
    }

   int imid=first+(last-first)/2;

   if(first==last || imid==first)
   {
        return -1;
   }
   if(values[imid]>key)
   {
        return findIndex(values,key,first,imid);
    }
    else if(values[imid]<=key)
    {
        return findIndex(values,key,imid,last);
    }

}

我觉得这更符合您正在寻找的内容......而且我们不会在这个东西的最后一个值上废话

于 2013-05-17T20:31:18.793 回答
0 
/* binary_range.c (c) 2016 adolfo@di-mare.com  */
/* http://stackoverflow.com/questions/10935635 */

/* This code is written to be easily translated to Fortran */

#include <stdio.h>   /* printf() */
#include <assert.h>  /* assert() */

/** Find the biggest index 'i' such that '*nSEED <= nVEC[i]'.
    - nVEC[0..N-1] is an strict ascending order array.
    - Returns and index in [0..N].
    - Returns 'N' when '*nSEED>nVEC[N-1]'.
    - Uses binary search to find the range for '*nSEED'.
*/
int binary_range( int *nSEED, int nVEC[] , int N ) {
    int lo,hi, mid,plus;

    if ( *nSEED > nVEC[N-1] ) {
        return N;
    }
    for (;;) { /* lo = binary_range_search() */
        lo = 0;
        hi = N-1;
        for (;;) {
            plus = (hi-lo)>>1; /* mid = (hi+lo)/2; */
            if ( plus == 0 ) {   assert( hi-lo==1 );
                if (*nSEED <= nVEC[lo]) {
                    hi = lo;
                }
                else {
                    lo = hi;
                }
            }
            mid = lo + plus; /* mid = lo + (hi-lo)/2; */

            if (*nSEED <= nVEC[mid]) {
                hi = mid;
            }
            else {
                lo = mid;
            }
            if (lo>=hi) { break; }
        }
        break;
    } /* 'lo' is the index */
    /* This implementation does not use division. */
    /* =========================================  */

    assert( *nSEED <= nVEC[lo] );
    return lo;
}

/** Find the biggest index 'i' such that '*nSEED <= nVEC[i]'.
    - nVEC[0..N-1] is an strict ascending order array.
    - Returns and index in [0..N].
    - Returns 'N' when '*nSEED>nVEC[N-1]'.
    - Uses sequential search to find the range for '*nSEED'.
*/
int sequential_range( int* nSEED, int nVEC[] , int N ) {
    int i;
    if ( *nSEED > nVEC[N-1] ) {
        return N;
    }
    i=0;
    while ( i<N ) {
        if ( *nSEED <= nVEC[i] ) { break; }
        ++i;
    }
    return i;
}

/** test->stackoverflow.10935635(). */
void test_10935635() {
{{  /* test.stackoverflow.10935635()                                  */
    /* http://stackoverflow.com/questions/10935635                    */
    /* binary_range search to find the range in which the number lies */
    /*              0  1  2  3  4                                     */
    int nVEC[] = { 12,20,32,40,52 }; int val;
    int N = sizeof(nVEC)/sizeof(nVEC[0]); /* N = DIM(nVEC[]) */

    val=19; val   = binary_range( &val,nVEC,N );

    /* 19 -> [12 < (19) <= 20] -> return 1 */
    val=19; assert( binary_range( &val,nVEC,N ) == 1 );

    /* 22 -> [20 < (22) <= 32] -> return 2 */
    val=22; assert( binary_range( &val,nVEC,N ) == 2 );

    /* 40 -> [32 < (40) <= 40] -> return 3 */
    val=40; assert( binary_range( &val,nVEC,N ) == 3 );

    /* Everything over 52 returns N */
    val=53; assert( binary_range( &val,nVEC,N ) == N );
}}
}

/** Test program. */
int main() {
    if (1) {
        printf( "\ntest_10935635()" );
        test_10935635();
    }
    printf( "\nEND" );
    return 0;
}

/* Compiler: gcc.exe (tdm-1) 4.9.2 */
/* IDE:      Code::Blocks 16.01    */
/* Language: C && C++              */

/* EOF: binary_range.c */
于 2016-07-16T21:11:06.313 回答
0

我知道这是一个旧线程，但由于我必须解决类似的问题，我想我会分享它。给定一组不重叠的整数范围，我需要测试给定值是否位于任何这些范围内。以下（在 Java 中）使用修改后的二进制搜索来测试值是否位于已排序（从最低到最高）的整数范围集中。

/**
 * Very basic Range representation for long values
 *
 */
public class Range {

private long low;
private long high;

public Range(long low, long high) {
    this.low = low;
    this.high = high;
}

public boolean isInRange(long val) {
    return val >= low && val <= high;
}

public long getLow() {
    return low;
}

public void setLow(long low) {
    this.low = low;
}

public long getHigh() {
    return high;
}

public void setHigh(long high) {
    this.high = high;
}

@Override
public String toString() {
    return "Range [low=" + low + ", high=" + high + "]";
}
}



import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//Java implementation of iterative Binary Search over Ranges
class BinaryRangeSearch { 
// Returns index of x if it is present in the list of Range, 
// else return -1 
int binarySearch(List<Range> ranges, int x) 
{ 

    Range[] arr = new Range[ranges.size()];
    arr = ranges.toArray(arr);
    int low = 0, high = arr.length - 1; 
    int iters = 0;
    while (low <= high) { 
        int mid = low + (high - low) / 2; // find mid point

        // Check if x is present a
        if (arr[mid].getLow() == x) {
            System.out.println(iters + " iterations");
            return mid;                 
        }

        // If x greater, ignore left half 
        if (x > arr[mid].getHigh()) {
            low = mid + 1; 
        }
        else if (x >= arr[mid].getLow()) {
            System.out.println(iters + " iterations");
            return mid;
        }

        // If x is smaller, ignore right half of remaining Ranges
        else
            high = mid - 1; 
        iters++;
    } 

    return -1; // not in any of the given Ranges
} 

// Driver method to test above 
public static void main(String args[]) 
{ 
    BinaryRangeSearch ob = new BinaryRangeSearch(); 

    // make a test list of long Range
    int multiplier = 1;

    List<Range> ranges = new ArrayList<>();
    int high = 0;
    for(int i = 0; i <7; i++) {

        int low = i + high;
        high = (i+10) * multiplier;
        Range r = new Range(low, high);
        multiplier *= 10;
        ranges.add(r);
    }

    System.out.println(Arrays.toString(ranges.toArray()));

    int result = ob.binarySearch(ranges, 11); 
    if (result == -1) 
        System.out.println("Element not present"); 
    else
        System.out.println("Element found at "
                        + "index " + result); 
} 
}
于 2019-02-09T14:25:50.957 回答
0

我的python实现：

时间复杂度：O(log(n)) 空间复杂度：O(log(n))

def searchForRange(array, target):
    range = [-1, -1]
    alteredBinarySerach(array, target, 0, len(array) -1, range, True)
    alteredBinarySerach(array, target, 0, len(array) -1, range, False)
    return range

def alteredBinarySerach(array, target, left, right, range, goLeft):
    if left > right:
        return

    middle = (left+ right)//2

    if array[middle] > target:
        alteredBinarySerach(array, target, left, middle -1, range, goLeft)
    elif array[middle] < target:
        alteredBinarySerach(array, target, middle +1, right, range, goLeft)
    else:
        if goLeft:
            if middle == 0 or array[middle -1] != target:
                range[0] = middle
            else:
                alteredBinarySerach(array, target, left, middle -1 , range, goLeft)
        else:
            if middle == len(array) -1 or array[middle+1] != target:
                range[1] = middle
            else:
                alteredBinarySerach(array, target, middle +1, right , range, goLeft)
于 2019-12-01T10:41:44.013 回答