首页 > 代码库 > 位运算符 优先级 折半搜索
位运算符 优先级 折半搜索
看编程珠玑,深知二分搜索的用处之大,自己写了一遍,竟然出了死循环。代码如下:
1 int bsearch(int *data, int val,int left, int right) 2 { 3 if(left <= right) 4 { 5 int mid = left + (right-left)>>1; 6 if(data[mid]==val) 7 return mid; 8 else if(data[mid]<val) 9 return bsearch(data,val,mid+1,right);10 else11 return bsearch(data,val,left,mid-1);12 }13 else14 return -1;15 }
感觉没有特殊的地方,经过调试发现,第5行,当left = 5 ,right = 9时,mid = 5 + (9-5)>>1;结果是4 !!!!为何不是7? 运算符优先级,+号 高于 位运算符。 相当于 (5 + (9-5))>>1 ,刚好数组内data[4] < val ,造成死循环。。。
附1、折半搜索的递归和非递归实现:
1 #include <cstdio> 2 #include <algorithm> 3 4 using namespace std; 5 6 //递归实现 7 int bsearch(int *data, int val,int left, int right) 8 { 9 if(left <= right)10 {11 int mid = left + ((right-left)>>1);12 if(data[mid]==val)13 return mid;14 else if(data[mid]<val)15 return bsearch(data,val,mid+1,right);16 else17 return bsearch(data,val,left,mid-1);18 }19 else20 return -1;21 }22 //非递归实现 23 int bsearch2(int *data,int val,int left,int right)24 {25 while(left <=right)26 {27 int mid = left + ((right-left)>>1);28 if(data[mid]==val)29 return mid;30 else if(data[mid]<val)31 left = mid+1;32 else33 right = mid-1;34 }35 return -1;36 }37 38 int main()39 {40 int d[]={41 5,6,7,24,698,45,698,41,547,342 };43 sort(d,d+10);44 printf("%d\n",bsearch2(d,3,0,9));//调用时,left为0,right为n-1 45 46 return 0; 47 }
附2、运算符优先级:
优先级 | 运算符 | 名称或含义 | 使用形式 | 结合方向 | 说明 |
1 | [] | 数组下标 | 数组名[常量表达式] | 左到右 | |
() | 圆括号 | (表达式)/函数名(形参表) | |||
. | 成员选择(对象) | 对象.成员名 | |||
-> | 成员选择(指针) | 对象指针->成员名 | |||
2 | - | 负号运算符 | -表达式 | 右到左 | 单目运算符 |
(类型) | 强制类型转换 | (数据类型)表达式 | |||
++ | 自增运算符 | ++变量名/变量名++ | 单目运算符 | ||
-- | 自减运算符 | --变量名/变量名-- | 单目运算符 | ||
* | 取值运算符 | *指针变量 | 单目运算符 | ||
& | 取地址运算符 | &变量名 | 单目运算符 | ||
! | 逻辑非运算符 | !表达式 | 单目运算符 | ||
~ | 按位取反运算符 | ~表达式 | 单目运算符 | ||
sizeof | 长度运算符 | sizeof(表达式) | |||
3 | / | 除 | 表达式/表达式 | 左到右 | 双目运算符 |
* | 乘 | 表达式*表达式 | 双目运算符 | ||
% | 余数(取模) | 整型表达式/整型表达式 | 双目运算符 | ||
4 | + | 加 | 表达式+表达式 | 左到右 | 双目运算符 |
- | 减 | 表达式-表达式 | 双目运算符 | ||
5 | << | 左移 | 变量<<表达式 | 左到右 | 双目运算符 |
>> | 右移 | 变量>>表达式 | 双目运算符 | ||
6 | > | 大于 | 表达式>表达式 | 左到右 | 双目运算符 |
>= | 大于等于 | 表达式>=表达式 | 双目运算符 | ||
< | 小于 | 表达式<表达式 | 双目运算符 | ||
<= | 小于等于 | 表达式<=表达式 | 双目运算符 | ||
7 | == | 等于 | 表达式==表达式 | 左到右 | 双目运算符 |
!= | 不等于 | 表达式!= 表达式 | 双目运算符 | ||
8 | & | 按位与 | 表达式&表达式 | 左到右 | 双目运算符 |
9 | ^ | 按位异或 | 表达式^表达式 | 左到右 | 双目运算符 |
10 | | | 按位或 | 表达式|表达式 | 左到右 | 双目运算符 |
11 | && | 逻辑与 | 表达式&&表达式 | 左到右 | 双目运算符 |
12 | || | 逻辑或 | 表达式||表达式 | 左到右 | 双目运算符 |
13 | ?: | 条件运算符 | 表达式1? 表达式2: 表达式3 | 右到左 | 三目运算符 |
14 | = | 赋值运算符 | 变量=表达式 | 右到左 | |
/= | 除后赋值 | 变量/=表达式 | |||
*= | 乘后赋值 | 变量*=表达式 | |||
%= | 取模后赋值 | 变量%=表达式 | |||
+= | 加后赋值 | 变量+=表达式 | |||
-= | 减后赋值 | 变量-=表达式 | |||
<<= | 左移后赋值 | 变量<<=表达式 | |||
>>= | 右移后赋值 | 变量>>=表达式 | |||
&= | 按位与后赋值 | 变量&=表达式 | |||
^= | 按位异或后赋值 | 变量^=表达式 | |||
|= | 按位或后赋值 | 变量|=表达式 | |||
15 | , | 逗号运算符 | 表达式,表达式,… | 左到右 | 从左向右顺序运算 |
上表参考: http://www.slyar.com/blog/c-operator-priority.html