本文利用Java实现二分法查找 思想： 在二分查找算法中，数列已经排好序，对于要搜索的数字，我们从中间的数开始搜索，如果目标数小于中间数，则无需搜索右边的数，因为右边的数都大于中间的数，直接搜索左边的数就可以；如果目标数大于中间数，则无需搜索左边的数，因为左边的数都是小于中间数，直接搜索右边的数 注意的地方： 1、数列是排好序的，否则无法进行二分法查找 2、数列中的元素的值不能重复 3、注意if语句的判断方式，怎么处理结果 算法时间复杂度和空间复杂度： 1、最坏情况是找第一个元素或是最坏一个元素，T(n)=O(logn) 2、最好的情况是要查找最中间的元素，O(1) 空间复杂度是S(n)=n Java代码实现
/* The guess API is defined in the parent class GuessGame. @param num, your guess @return -1 if my number is lower, 1 if my number is higher, otherwise return 0 int guess(int num); */ public class Solution extends GuessGame { public int guessNumber(int n) { int i=1; int j=n; int mid=0; //使用二分法查找 while(i<=j){ //求中间数 mid=(j-i)/2+i; //guess(int num)是用来返回目标值比你猜的这个数是高了还是低了 int val=guess(mid); //-1表示我的数字比你猜的数字要小 if(val==-1) j=mid-1; else if(val==1) //+1表示我的数字比你猜的数字要大 i=mid+1; else return mid; } return -1; } }