假设已经给定了一个数组并且想要在该数组中查找元素，您如何使用二进制搜索来搜索该数组中的元素，并且给定的数组已经排序并且数组的大小是未知的。可以应用线性搜索，但我试图找出比线性算法更快的搜索。
问问题
11794 次
7 回答
10
如果您可以测试您是否已超出数组范围，那么您可以使用修改后的二进制搜索（假设基于 1 的数组）：
- 下 = 1，上 = 1；
- while (A[upper] < 元素) 上 *= 2;
- 正常的二进制搜索（下，上）。
否则，没有真正的方法可以做到这一点：假设您在某个地方找到了与您需要的元素相等的东西，您无法知道它是否已经从数组中掉出来。
于 2013-05-13T00:36:29.143 回答
2
假设数组A已排序（否则不能进行二分查找），并且要查找的元素是k，则可以找到一个索引i，使得k < A[i]，然后从1开始二分查找到 i（1 索引数组）。这是因为一旦 k < A[i]，就保证在已排序元素 A[1..i] 的范围内找到（或未找到）k。
要找到索引 i，您将从 i = 1 开始，如果 k > A[i]，则将其加倍。这就像二进制搜索，除了你将搜索范围加倍，所以它仍然会有 O(log n) 的运行时间。
该算法类似于：设置 i = 1，然后重复直到 k <= A[i]：
- 如果 k > A[i] 则令 i = i*2
如果 k == A[i]，那么你就完成了，否则像往常一样在 A[1..i] 上进行二进制搜索。
于 2013-05-13T04:22:42.620 回答
1
以下应该可以工作（尚未测试），但应该具有与二进制搜索相同的界限，O(log(n))：
private bool hasValue(int[] array, int search, int start, int end)
{
int mid = (start+end)/2;
try
{
//Check to see if we can grab the value
int value = array[mid];
//If we are here, we are in the array
//Perform the binary search
if (value==search)
return true;
else if (end <= start)
return false;
else if (value>search)
return hasValue(array, search, start, mid);
else
return hasValue(array, search, mid, end*2);
}
catch(ArrayIndexOutOfBoundsException e)
{
//If we are here, then we were outside the array, so
//loop through the lower half
return hasValue(array, search, start, mid);
}
}
public bool hasValue(int[] array, int search)
{
// 0 is the start of the array (known)
// 1 is the end--start with any number that is greater than max(start, 1)
return hasValue(array, search, 0, 1);
}
这是一个示例用法
// 2 is the value you are looking for
bool hasTwo = hasValue(array, 2);
于 2013-05-13T01:17:13.117 回答
0
这个对我有用，这是 O(log N + log N)，即仍然是 O(log N)？这也以一种有效的方式拟合子阵列。O(log N)
static int bSearch (int needle, int[] arr)
{
boolean done = false;
int i = 1;
int lower = 0;
int upper = 1;
int temp;
while (!done)
{
try{
if (needle == arr[upper])
return upper;
else if (needle > arr[upper])
{
temp = lower;
lower = upper;
upper = temp + (int) Math.pow(2,i);
i = i + 1;
}
else
{
done = true;
break; //found the upper bounds
}
}
catch (IndexOutOfBoundsException e)
{
upper = (upper -lower) / 2;
i = 0;
}
}
if (done == true)
//do normal binary search with bounds lower and upper and length upper-lower
else
return -1;
}
于 2013-09-03T12:31:26.923 回答
0
这是一个开始：
我可能会尝试这样的事情（用Java-esqe语言）。（假设一个整数数组）
int endOfArray = 10;
try {
while (true) {
int value = theArray[endOfArray*2];
if (value > requestedValue) // good enough
return doBinarySearch(theArray, 0, endOfArray, requestedValue);
else
endOfArray*=2;
}
}
catch (ArrayIndexOutOfBoundsException aioob) {
// we know that the end of the array is less than endOfArray*2 but > endOfArray
// do something clever here TBD. :-)
}
稍后添加的注释：如果数组是“C-like”并且末尾有 0，您还必须检查它。顺便说一句，如果有人对“这里有一些聪明的东西”部分有一个简单的解决方案，请随时编辑答案。
于 2013-05-13T00:58:30.727 回答
0
import java.util.Scanner;
public class SolutionB {
int size;
int arr[];
int M;
void inputData(){
Scanner in = new Scanner(System.in);
size = in.nextInt();
M = in.nextInt();
arr = new int[size + 1];
for(int i = 1; i <= size; i+=1){
arr[i] = in.nextInt();
}
}
void findMIndex(){
int start = 1;
int end = 2;
int j = 0;
int flag = 0, flag2=0;
for (int i = 2; flag == 0; ) {
try{
if (arr[end] > M) {
flag = 1;
}
else if (arr[end] == M) {
System.out.println(end);
return;
}
else if(start == end) {
flag=1;
flag2=1;
}
else {
i *= 2;
start = end;
end = i;
}
}
catch (ArrayIndexOutOfBoundsException e){
end = start + (end - start)/2;
}
}
if(flag2==0)
{
binary(start, end);
}
else
{
System.out.println("NOT_FOUND");
return;
}
}
void binary(int start, int end){
int index = -1;
while( start <= end ){
int mid = (start + ( end - 1 )) / 2 + 1;
if( M == arr[mid] ){
index = mid;
break;
}
else if(M < arr[mid]){
end = mid - 1;
}
else {
start = mid + 1;
}
}
if( index == -1 ){
System.out.println("NOT_FOUND");
}
else{
System.out.println(index);
}
}
public static void main(String[] as){
SolutionB obj = new SolutionB();
obj.inputData();
obj.findMIndex();
}
}
此解决方案适用于 1 索引数组。这个对我有用。
于 2019-08-25T16:08:04.767 回答
0
Python 解决方案：如果元素存在于数组中，此方法将有效
def searchArray(nums, element):
if nums[0] == element: return 0
i = 1
base = 0
done = False
while not done:
try:
if nums[base + i] == element:
print('if')
return base + i
elif nums[i] < element:
print('elif')
i = i * 2
else:
print('else')
done = True
print('base, i', base, i)
base = base + i//2
i = 1
except:
print('out of bound base, i', base, i)
base = base + i//2
i = 1
nums = [2, 3, 5, 6, 8, 9, 10, 11]
print(searchArray(nums, 11))
于 2020-07-18T02:28:34.493 回答