(lintcode)第14题二分查找

要求&＃xff1a;给定一个排序的整数数组&＃xff08;升序&＃xff09;和一个要查找的整数target&＃xff0c;用O(logn)的时间查找到target第一次出现的下标&＃xff08;从0开始&＃xff09;&＃xff0c;如果target不存在于数组中&＃xff0c;返回-1。

样例&＃xff1a;在数组 [1, 2, 3, 3, 4, 5, 10] 中二分查找3&＃xff0c;返回2。

思路&＃xff1a;使用递归&＃xff0c;每次都找到中间那个数进行判断&＃xff0c;直到区间第一个数的下标等于最后一个数的下标。判断的时候&＃xff0c;对中间的数进行判断&＃xff0c;分为3种情况&＃xff0c;一种是刚好等于我们要找的数&＃xff0c;这时候不能够直接返回下标&＃xff0c;因为我们不确定这个数的前面是否存在着同样的数&＃xff0c;所以&＃xff0c;要对这个数前面的数进行查找&＃xff0c;找到就返回前面的&＃xff0c;没找到就返回中间数的下标

&＃xff0c;当中间数小于目标数时&＃xff0c;查找后一半&＃xff0c;当中间数大于目标数的时候&＃xff0c;查找前面一半。递归直到区间只有一个数。

代码如下&＃xff1a;

class Solution {/*** &＃64;param nums: The integer array.* &＃64;param target: Target to find.* &＃64;return: The first position of target. Position starts from 0.*/public int binarySearch(int[] nums, int target) {//write your code herereturn search(nums,target,0,nums.length);}public int search(int []nums,int target,int first,int last){if(first&＃61;&＃61;last){if(nums[first]&＃61;&＃61;target)return first;else return -1;}else{int avg&＃61;(first&＃43;last)/2;if(nums[avg]&＃61;&＃61;target){if(search(nums,target,first,avg)&＃61;&＃61;-1)//查找前一半有没有相同的数return nums[avg];elsereturn search(nums,target,first,avg);}else if(nums[avg]>target)return search(nums,target,first,avg);else if(nums[avg]}

如果有所帮助&＃xff0c;脸皮厚求个赞~

此文章仅代表自己&＃xff08;本菜鸟&＃xff09;学习积累记录&＃xff0c;或者学习笔记&＃xff0c;如有侵权&＃xff0c;请联系作者删除。人无完人&＃xff0c;文章也一样&＃xff0c;文笔稚嫩&＃xff0c;在下不才&＃xff0c;勿喷&＃xff0c;如果有错误之处&＃xff0c;还望指出&＃xff0c;感激不尽~

技术之路不在一时&＃xff0c;山高水长&＃xff0c;纵使缓慢&＃xff0c;驰而不息。

公众号&＃xff1a;秦怀杂货店