剑指offer--查找算法（简单）(JAVA版)

小咪咪 2024-04-06 12:53 48阅读 0赞

坚持算法的每一天都是新的收获,本期讲解的几道算法是基本的查找算法,大家加油!!!!!

### 简单的查找算法 ###

#### 1.[剑指 Offer 53 - I. 在排序数组中查找数字 I][Offer 53 - I. _ I] ####

题目:

统计一个数字在排序数组中出现的次数。

示例 1:

输入: nums = \[5,7,7,8,8,10\], target = 8  
输出: 2  
示例 2:

输入: nums = \[5,7,7,8,8,10\], target = 6  
输出: 0

思路:

由于数组已经排序，因此整个数组是**单调递增**的，我们可以利用二分法来加速查找的过程。 考虑target在数组出现的次数,我们只需要找到target第一次出现的位置left和第一个大于target的位置right,当target存在的话次数便是right-left+1,从代码中得到更好的理解吧

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

题目  
[  
剑指 Offer 53 - II. 0～n-1中缺失的数字][_ Offer 53 - II. 0_n-1]

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

**示例 1:**

输入: [0,1,3]
    输出: 2

**示例 2:**

输入: [0,1,2,3,4,5,6,7,9]
    输出: 8

思路:在有序数字中查找最好的方法就是二分法 如果中间值等于本身,返回左边+1,否则令右边赋值中间数减一,二分一直查下去,直接上代码

**目录**

简单的查找算法

1.剑指 Offer 53 - I. 在排序数组中查找数字 I

--------------------

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

[Offer 53 - I. _ I]: https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
[_ Offer 53 - II. 0_n-1]: https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/