LeetCode <二分搜索>34.Find First and Last Position of Element in Sorted Array

34.Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

题目大意:这个是一个有序数组中查找一个数子出现的起始位置和终止位置,如果没有这个数字返回[-1,-1];

解法:

解题思路:有序数组,题目要求的复杂度为O(logn),很容易想到采用二分查找法。但是本题采用的二分查找法与一般的二分查找法有所不同,这里我们要找到第一次和最后一次出现的target值,因此我们就不能找到了target值后就立即返回,而是应该继续搜索,直到找到最左边和最后边的target值。

    public int[] searchRange(int[] nums, int target) {
        return new int[]{findFirstOrLast(nums,target,true),findFirstOrLast(nums,target,false)};
    }
    
    public int findFirstOrLast(int[] nums, int target,boolean firstOrLast){
        int resIndex = -1;
        int left = 0;
        int right = nums.length-1;
        int mid;
        while (left<=right){
            mid = left + (right - left)/2;
            if (firstOrLast)
                if (nums[mid]>=target) right = mid -1;
                else left = mid+1;
            else  
                if (nums[mid]<=target) left = mid+1;
                else right = mid-1;
            if (nums[mid] == target) resIndex = mid;
        }
        return resIndex;
    }

上面程序中,firstOrLast为true时,寻找Fisrt,为false时候,寻找last。

public static int Binary(int[] arr, int key, int low, int high) {
		while (low <= high) {
			int mid = (low + high) / 2;
			if (arr[mid] > key) {
				high = mid - 1;
			} else if (arr[mid] < key) {
				low = mid + 1;
			} else {
				return mid;
			}
		}
		return -1;
	}
	
	
	
	
	
	      while (left<=right){
           mid = left + (right - left)/2;
           if (nums[mid]>=target) right = mid -1;
           else left = mid+1;
           if (nums[mid] == target) resIndex = mid;
        }
	
	
	
	
 if (nums[mid] == target) resIndex = mid; Look at this step after the if_else conditions are done. In
 FIndFirst, he makes idx move towards the lower index, and in FIndLast he makes it move towards the
 higher index. The loop doesn't exist even if the target is found, it moves to one end, (left==right) 
 and then exits. It's really smart!

二、旋转数组的最小元素

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1

    public int minNumberInRotateArray(int [] array) {
        if(array.length == 0) return 0;
          
        int left = 0;
        int right = array.length-1;
        while(left<=right){
            int mid = left + (right - left)/2;
         
            if(mid-1>0 && array[mid]<array[mid-1]){
                return array[mid];
            }
            // 说明左半部分是递增的
            if (array[left]<array[mid]){
                 left = mid + 1;
            }
            // 说明右半部分是递增的
            if (array[right]>array[mid]){
                 right = mid - 1;
            } 
        }
         return 0;
    }

总结:

不管是那种方法,即使是相等的情况也要查找,因此必须while()加上等于号

不同点:

  1. 不直接返回,采用变量记录 if(nums[mid]== target) resIndex = mid;
  2. nums[mid]>=target 含有等于号
  3. 注意不是大于小于等于三选一,等于必须要,大于小于是二选一

这个解法比较巧妙的是可以获取到最前和最后出现的值target值,这个与以往的二分搜索不同在于:不能找到了target值后就立即返回,而是应该继续搜索。在有序的数组中查找,我们首先应该想到的就是采用二分搜索。二分搜索也有一些变形,例如《LeetCode 33 & 81 Search in Rotated Sorted Array I&II》,需要好好消化。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏TechBox

数据结构与算法之线性表前言线性表

1925
来自专栏架构之路

Combination Sum II 组合数求和之2-Leetcode

原题: Given a collection of candidate numbers (C) and a target number (T), find al...

3065
来自专栏desperate633

LintCode 子集题目代码

813
来自专栏用户3030674的专栏

Java 工具类—日期获得,随机数,系统命令,数据类型转换

1461
来自专栏自学笔记

Data Structurestackheapheap的实现索引堆tree并查集图 Graph

堆的基本性质: ①堆中的某一个节点总是不小于或不大于其父节点的值。 ②堆总是一棵完全二叉树 比较经典的堆有二叉堆,费波纳茨堆等等。如果一棵二叉树最下层上的...

1013
来自专栏Android机动车

数据结构学习笔记——线性表(中)

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的。这就意味着,这些数据元素可以存在内存未被占用的...

913
来自专栏电光石火

HashSet/HashMap详解

HashMap和HashSet是Java Collection接口两个重要的成员,其中HashMap是Map接口常用的实现类,HashSet是Set接口常用...

23410
来自专栏Java技术栈

Java List面试题汇总

1、你知道的List都有哪些? 2、List和Vector有什么区别? 3、List是有序的吗? 4、ArrayList和LinkedList的区别?分别用在什...

3939
来自专栏weixuqin 的专栏

数据结构学习笔记(线性表)

3085
来自专栏java一日一条

Java 容器&泛型(1):认识容器

容器是Java语言学习中重要的一部分。泥瓦匠我的感觉是刚开始挺难学的,但等你熟悉它,接触多了,也就“顺理成章”地知道了。Java的容器类主要由两个接口派生而出:...

1202

扫码关注云+社区

领取腾讯云代金券