题目
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
暴力查找
直接找。。遍历
直接尝试二分查找
- 递归应该要用
- 中间的值。。 a b c d e
- 怎么截取数组????下标来做
- 0 1 2 3 4 5 6 7 8 9 里面找8
len 10,mid 5;nums[5] = 5;
6 > nums[5],
mid = (10 - 5 )/2+ 5 = 7
6< nums[7]
mid =
5.
从这开始就逐渐理解了
要有两个,一个left、一个right,两个就能界定死,上一个mid要保存
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
找16
left = 0,right = 20,mid = 10
if >nums[mid]
left = mid ,mid = (left+right)*1/2
if <nums[mid]
right = mid;mid = (left+right)*1/2
if =nums[mid]
return mid;
循环终止条件
right == left
收获
- 数组长度nums.size()
- 关键代码分析:
`}else if(target > nums[mid]){
left = mid+1;
//小于的话在下半部分找
}else if(target < nums[mid]){
right = mid-1;`
这里为什么要加1和减1,刚开始也是没想到这,但提交的时候报错了,出现死循环了,原来是mid会循环赋给left同一个值,所以这就得加一减一,这个对结果没影响吗???对,没有影响,因为加一减一错过的是mid,而mid已经验证过了
4. 循环终止条件是left>right,之前一直因为left = right了就循环结束了,一直报错,后面改了条件left>right也就是两个都交错过了再结束,一下就过了,上面的加一减一就是让最后不会死循环,能够中止循环的。
看别人的题解的收获:
实际使用求中间mid索引建议用这种方法:int mid = left + (right-left)/2;
可以防止left+right溢出(超出整数范围)。