在排序数组中进行二进制搜索的递归算法的问题 [英] Thr problem of the recursive algorithm to do binary search in a sorted array

问题描述

我想要一个订单数组的二进制搜索算法。

  int  Array ::搜索（ int  target， int  * start， int  * tail）{
  if （start> tail）{
 cout<<   找不到<< endl; 
 返回  -   1 ; 
} 
  int  offsetMid =（tail-start）/ 2 / sizeof（ int ）;  //  以int为单位 
 cout<<   offset：<< offsetMid<<   mid<< *（start + offsetMid）<< endl; 
 cout<<< start<<  << tail<< ENDL; 
  if （target == *（start + offsetMid））{
 cout<<    mid<< endl; 
  return （offsetMid + 1）; 
} 
  if （*（start + offsetMid）> target）{
 cout<<   left<< endl; 
 tail = start +（offsetMid-  1 ）*  sizeof （ INT ）; 
  return 搜索（target，start，tail）; 
} 
  if （*（start + offsetMid）< target）{
 cout<<   right<< endl; 
 start = start +（offsetMid）*  sizeof （ int ）; 
  return 搜索（target，start，tail）; 
} 
} 

但它不起作用，我知道func的参数应该更好地是数组的索引而不是请问，我只想尝试这种方式。我使用的编译器是

 gcc版本6.2.1 20160916（Red Hat 6.2.1-2）（GCC）

另一个奇怪的事情

 int offsetMid =（tail -start）/ 2 / sizeof（int）; //以int为单位

tail和start都是int *的类型，但是它们的区别是按字节计算的，所以我必须将它除以通过sizeof（int）获取偏移值。

 if（*（start + offsetMid）> target）

但是当我想将偏移值加到起始地址时获取特定位置的值，我不应该通过sizeof（int）计算它.WHY ??



我尝试了什么：



我试图打印起点和终点的地址，以及中间位置的元素值。

解决方案

我看到的问题是你用sizeof（int）来调整你的指针。因为它们已经被声明为int指针，所以指针的任何加法或减法都由编译器通过sizeof（int）进行调整。

即

  int  * pi =  //  有效指针;  
  void  * pv =（ void  *）pi; 
 
  bool  bAdj =（pi +  1 ）==（pv + < span class =code-keyword> sizeof （ int ））;  //  返回true  

尾巴和start是int *的类型，但它们的区别是按字节计算的，所以我必须用sizeof（int）除以得到偏移值。

错误！ 这是由语言定义的（与您使用的编译器无关）。减去这两个指针将返回适合此处的整数。

当你不理解你的代码正在做什么或为什么它做它做的时候，答案是调试器。

使用调试器查看代码正在执行的操作。它允许你逐行执行第1行并在执行时检查变量，它是一个令人难以置信的学习工具。



调试器 - 维基百科，免费的百科全书 [ ^ ]



调试器在这里向您展示您的代码正在做什么，您的任务是与它应该做什么进行比较。

调试器中没有魔法，它没有找到错误，它只是帮助你。当代码没有达到预期的效果时，你就接近了一个bug。

tl; dr：

你可能想检查一下你的测试代码调用搜索功能 - 也许错误就在那里！



长版：



这不是一个独立的解决方案，但只是解决方案1的验证。我只是为了代码格式化而使用解决方案表单：



使用此测试代码，我可以验证解决方案1是否正确：

  #include   <   iostream  >  
  使用 std :: cout; 
 使用 std :: endl; 
 
  int 搜索（ int  target， int  * start， int  * tail）{
  if （start> ; tail）{
 cout<<  找不到<< endl; 
 返回  -   1 ; 
} 
  int  offsetMid =（tail-start）/ 2  / *  < span class =code-comment> / sizeof（int）* / ;  //   by unit of int  
 cout<<   offset：<< offsetMid< ;<   mid<< *（start + offsetMid）<< endl; 
 cout<<< start<<  << tail<< ENDL; 
  if （target == *（start + offsetMid））{
 cout<<    mid<< endl; 
  return （offsetMid + 1）; 
} 
  if （*（start + offsetMid）> target）{
 cout<<   left<< endl; 
 tail = start +（offsetMid-  1 ） / *   *的sizeof（int）的* / ; 
  return 搜索（target，start，tail）; 
} 
  if （*（start + offsetMid）< target）{
 cout<<   right<< endl; 
 start = start +（offsetMid） / *   * sizeof（int）* / ; 
  return 搜索（target，start，tail）; 
} 
} 
  void  test_Search（）{
  int  arr [] = { 2 ， 5 ， 6 ， 14 ， 44 ， 51 ， 94 ， 221 ， 356  ， 444 }; 
  int  * start = arr; 
  size_t  length =  sizeof （arr）/ sizeof（ INT ）; 
 cout<<长度<< ENDL; 
  int  * end = start + length; 
  int  s =搜索（ 6 ，start，end）; 
 cout<< s<< ENDL; 
} 

这会产生输出：

 10 
抵消：5月中旬51 
 0033FA60 0033FA88 
剩余
抵消：2 mid 6 
 0033FA60 0033FA70 
 
 $ b $ 

注意在测试函数中我如何通过明确地将数组的大小除以 sizeof（int）来计算数组的结束地址。这是必要的，因为在 int 指针中添加一个数字会使地址偏移量乘以 sizeof（int）：可疑这可能是你在遵循解决方案1的建议时无法重现预期结果的原因。


PS：编译器抱怨以下警告我没有懒得修理 - 但你应该：

引用：

警告C4715：'搜索'：并非所有控制路径都返回一个值

这很容易发现，但如果你不这样做，这里有一个提示：如果你在上面的数组中搜索11，那么会发生什么？ / BLOCKQUOTE>

I want to inplement a binary search algorithm of an order array.

int Array::Search(int target, int* start, int* tail){
	if(start>tail){
		cout<<"not find"<<endl;
		return -1;
	}
	int offsetMid= (tail-start)/2/sizeof(int);//by unit of int
	cout<<"offset: "<<offsetMid<<"  mid " <<*(start+offsetMid)<<endl;
	cout<<start<<" " <<tail<<endl;
	if(target == *(start+offsetMid) ){
		cout<<"mid"<<endl;
		return (offsetMid+1);
	}
	if(*(start+offsetMid) > target){
		cout<<"left"<<endl;
		tail = start+(offsetMid-1)*sizeof(int);
		return Search(target, start, tail);
	}
	if(*(start+offsetMid) < target){
		cout<<"right"<<endl;
		start = start+(offsetMid)*sizeof(int);
		return Search(target,start , tail);
	}
}

But it doesn't work, I know the parameter of the func should better be the index of the array rather than a pointor, I just want to try this way. The compiler I used is

gcc version 6.2.1 20160916 (Red Hat 6.2.1-2) (GCC) 

Another weird thing

int offsetMid= (tail-start)/2/sizeof(int);//by unit of int

Both tail and start are the type of int*, but the difference of them is counted by byte, so I must divide it by sizeof(int) to get the offset value.

if(*(start+offsetMid) > target)

But when I want to plus the offset value to the start address to get the value in a particular position, I shouldn't time it by sizeof(int).WHY??

What I have tried:

I have tried to print the addresses of both the start and end points, and the value of element in the middle position.

解决方案

The problem I see is you're adjusting your pointers by sizeof(int). As they are already declared as int pointers, any additions or subtractions to the pointers are adjusted by sizeof(int) by the compiler.
i.e.

int* pi = //a valid pointer;
void* pv = (void*)pi;

bool bAdj = (pi + 1) == (pv + sizeof(int)); // returns true

Both tail and start are the type of int*, but the difference of them is counted by byte, so I must divide it by sizeof(int) to get the offset value.

Wrong!! This is defined by the language (does not matter which compiler you use). The subtraction of these two pointers will return the number of ints that will fit in here.

When you don't understand what your code is doing or why it does what it does, the answer is debugger.
Use the debugger to see what your code is doing. It allow you to execute lines 1 by 1 and to inspect variables as it execute, it is an incredible learning tool.

Debugger - Wikipedia, the free encyclopedia[^]

The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't find bugs, it just help you to. When the code don't do what is expected, you are close to a bug.

tl;dr:
you might want to check your test code that calls the Search function - maybe the error is also there!

Long version:

This is not a stand-alone solution, but simply a verification for solution1. I'm only using the solution form for the sake of code formatting:

Using this test code, I could verify that solution 1 is correct:

#include <iostream>
using std::cout;
using std::endl;

int Search(int target, int* start, int* tail){
   if(start>tail){
      cout<<"not find"<<endl;
      return -1;
   }
   int offsetMid= (tail-start)/2/*/sizeof(int)*/;//by unit of int
   cout<<"offset: "<<offsetMid<<"  mid " <<*(start+offsetMid)<<endl;
   cout<<start<<" " <<tail<<endl;
   if(target == *(start+offsetMid) ){
      cout<<"mid"<<endl;
      return (offsetMid+1);
   }
   if(*(start+offsetMid) > target){
      cout<<"left"<<endl;
      tail = start+(offsetMid-1)/**sizeof(int)*/;
      return Search(target, start, tail);
   }
   if(*(start+offsetMid) < target){
      cout<<"right"<<endl;
      start = start+(offsetMid)/**sizeof(int)*/;
      return Search(target,start , tail);
   }
}
void test_Search() {
   int arr[] = {2, 5, 6, 14, 44, 51, 94, 221, 356, 444};
   int* start = arr;
   size_t length = sizeof(arr)/sizeof(int);
   cout << length << endl;
   int *end = start + length;
   int s = Search(6, start, end);
   cout << s << endl;
}

This produces the output:

10
offset: 5  mid 51
0033FA60 0033FA88
left
offset: 2  mid 6
0033FA60 0033FA70
mid
3

Note how in the test function I calculated the end address of the array by explicitely dividing the size of the array by sizeof(int). This is necessary, because adding a number to an int pointer imlpicitely multiplies the address offset by sizeof(int): Suspect that may be the reason why you could not reproduce the expected results when following the advice from solution 1.

P.S.: The compiler complained with the following warning which I did not bother to fix - but you should:

Quote:

warning C4715: 'Search' : not all control paths return a value

It's easy enough to spot, but if you don't, here's a tip: what will happen if you search in the above array for, say, the value 11?

这篇关于在排序数组中进行二进制搜索的递归算法的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！