博客

蓝桥杯备赛练习

1.二分查找

力扣：704题：给你一串有序的数据，查找出目标值target = x,若数据中没有该数据，返回 -1。

练习目的：熟悉数组的基本运用和基础的Java语法

解题思路：有序数据

暴力解法，就是直接遍历该数据，如果目标值相等直接返回该目标值的下标，那这意味着并没有使用到有序这个特点。

二分法如下：

难点

：对于边界值的取舍问题。容易混淆，保持一致。

• 如果是封闭区间，则端点相等时，该区间是有意义的 while(start <= end)，也就是 start = end,呢么对应的边界值一定不是目标值。直接 mid +1/ mid – 1
• 如果是半开区间,左闭右开，则端点相等时，该值区间是无意义的…while(start < end)。大于目标值时 end = mid ; 左闭右开即下一此比较是不会比较右端点值 。

class Solution {
    public int search(int[] nums, int target) {
       //查找有序的一串数字里的目标值。二分查找
       //1.确定三个值，中间值，两端值
       int mid  ;
       int start = 0;
       int end = nums.length -1;
       //2. 如果值不存在，则返回-1
       if(end < start) {
           return -1;
       }
       //3.当符合二分情况时，循环审查
       while(end >= start) {
           //4.更变查找区间
           mid = (start + end)/2;
           if(nums[mid] > target) {
               end = mid - 1;
           }
           else if(nums[mid] < target) {
               start = mid + 1;
           }
           //5.直至查找于中间值相等的数据
           else if(nums[mid] == target) {
               return mid;
           }
       }
       // 6.循环结束还没找到，就表示没有目标值
       return -1;
    }
}

掌握知识：数组是存储一类相同数据的容器，且是连续的，如若删除插入数据就需要移动其他数据。