查找算法之二分法查找

本文利用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;
    }
}