请实现无重复数字的升序数组的二分查找
给定一个 元素升序的、无重复数字的整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标(下标从 0 开始),否则返回 -1
数据范围: , 数组中任意值满足
进阶:时间复杂度 ,空间复杂度
[-1,0,3,4,6,10,13,14],13
6
13 出现在nums中并且下标为 6
[],3
-1
nums为空,返回-1
[-1,0,3,4,6,10,13,14],2
-1
2 不存在nums中因此返回 -1
数组元素长度在[0,10000]之间数组每个元素都在 [-9999, 9999]之间。
int search(int* nums, int numsLen, int target ) { int* left = nums; int* right = nums + numsLen - 1; int* middle = NULL; while(left <= right) { middle = left + (right - left) / 2; if(*middle < target) { left = middle + 1; } else if (*middle > target) { right = middle - 1; } else { return middle - nums; } } //走到这里。说明没有该元素 return -1; }
int search(int* nums, int numsLen, int target ) { if (!numsLen) return -1; else if (numsLen == 1 && nums[0] != target) return -1; else { int pos = numsLen / 2; if (nums[pos] == target) return pos; if (nums[pos] > target) return search(nums, pos, target); else { int j = search(nums + pos + 1, numsLen - pos - 1, target); if(j == -1) return -1; else return pos + 1 + search(nums + pos + 1, numsLen - pos - 1, target); } } }
int search(int* nums, int numsLen, int target ) { // write code here if(numsLen == 0) return -1; int left=0, right=numsLen-1; while(left<=right) { int mid = left+(right-left)/2; if(nums[mid]==target) return mid; if(nums[mid]<target) left=mid+1; if(nums[mid]>target) right=mid-1; } return -1; }
int search(int* nums, int numsLen, int target ) { int min = 0,max = numsLen-1,mid = (min+max)/2; while(max >= min) { if(target > nums[mid]) { min = mid+1; mid = (min+max)/2; } else if(target < nums[mid]) { max = mid-1; mid = (min+max)/2; } else { return mid; } } return -1; // write code here }
int search(int* nums, int numsLen, int target ) { if(numsLen==0) return -1; int left=0,right=numsLen-1,mid; while(left<=right){ //当left>right时停止 mid=(left+right)/2; if(nums[mid]>target) right=mid-1; else if(nums[mid]<target) left=mid+1; else return mid; } return -1; }
int search(int* nums, int numsLen, int target ) { // write code here int left=0; int right=numsLen-1; while(left<=right) { int mid=left+(right-left)/2; if(nums[mid]<target) { left=mid+1; } else if(nums[mid]>target) { right=mid-1; } else { return mid; } } return -1; }
int search(int* nums, int numsLen, int target ) { // write code here if(nums==NULL){ return -1; } int mid,left=0,right=numsLen-1; while(left<=right){ mid=(left+right)/2; if(nums[mid]<target) left=mid+1; else if(nums[mid]>target) right=mid-1; else (nums[mid]==target) return mid; } return -1;//在while中没有返回值则说明target在数组中无法找到返回-1 }