Day1 | 704、35

Day1 | 704、35
#一、二分查找
前提：有序、存在已知target
核心：数组中与target后，等于、小于、大于target的情况
注意：左开右闭和左闭右闭情况下边界值的处理

1.二分查找-左闭右闭

classSolution{publicintsearch(int[]nums,inttarget){//最左边的元素下标为0intleft=0;//最后一个元素下标是 nums.length-1intright=nums.length-1;while(left<=right){//在Java中/运算符是整数除法 结构是整数 舍去小数部分intmiddle=left+(right-left)/2;if(nums[middle]>target){right=middle-1;}elseif(nums[middle]<target){left=middle+1;}else{returnmiddle;}}return-1;}}

2.二分查找-左闭右开

classSolution{publicintsearch(int[]nums,inttarget){//左闭右开intleft=0;intright=nums.length;while(left<right){intmiddle=left+(right-left)/2;if(nums[middle]<target){right=middle+1;}elseif(nums[middle]>target){left=middle;}else{returnmiddle;}}return-1;}}

拓展题目:
搜索插入位置

classSolution{publicintsearchInsert(int[]nums,inttarget){//主要分四种情况//1.最前面 2.最后面 3.在中间 4.在中间有targetif(nums[0]>target){return0;}if(nums[nums.length-1]<target){returnnums.length;}intleft=0;intright=nums.length-1;while(left<=right){intmiddle=left+(right-left)/2;if(nums[middle]>target){right=middle-1;}elseif(nums[middle]<target){left=middle+1;}else{returnmiddle;}}returnleft;}}