初探二分法

推荐阅读

智能化校园：深入探讨云端管理系统设计与实现（一）
智能化校园：深入探讨云端管理系统设计与实现（二）

---

---

题目

题目：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

提示：

1. 你可以假设 nums 中的所有元素是不重复的。
2. n 将在 [1, 10000]之间。
3. nums 的每个元素都将在 [-9999, 9999]之间。

解法一

class Solution {
    public int search(int[] nums, int target) {
        for (int i=0;i<nums.length;i++){
            if (target==nums[i]){
                return i;
            }
        }
        return -1;
    }
}

解法二

看到题目给出的提示，数组为有序数组，数组元素不重复。这些不就是使用二分法的前提条件嘛。

class Solution {
    public int search(int[] nums, int target) {
        int left=0,right=nums.length-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if (nums[mid]==target)
                return mid;
            else if (nums[mid]<target)
                left=mid+1;
            else if (nums[mid]>target) 
                right=mid-1;
        }
        return -1;
    }
}

二分法代码模板：

int binarySearch(int [] nums,int target){
    int  left=0,right=X;//X 根据具体条件更改
    while(Y){//根据具体情况设定条件
        int mid=left+(right-left)/2;
        if(nums[mid]==target){
            ....
        }else if(nums[mid]<target){
            left=A;//根据具体条件更改
        }else if(nums[mid]>target){
            right=B;//根据具体条件更改
        }
    }
    return ....;
}