当前位置: 代码迷 >> 综合 >> 在转动的有序数组中寻找目标值
  详细解决方案

在转动的有序数组中寻找目标值

热度:33   发布时间:2024-01-16 12:15:55.0

DESC1:

题目描述

给出一个转动过的有序数组,你事先不知道该数组转动了多少
(例如,0 1 2 4 5 6 7可能变为4 5 6 7 0 1 2).
在数组中搜索给出的目标值,如果能在数组中找到,返回它的索引,否则返回-1。
假设数组中不存在重复项。

示例1

输入

[1],0

返回值

-1

示例2

输入

[3,2,1],1

返回值

2

CODE:

JAVA:

import java.util.*;public class Solution {/*** * @param A int整型一维数组 * @param target int整型 * @return int整型*/public int search (int[] A, int target) {// write code hereif (A == null || A.length == 0) {return -1;}int left = 0, right = A.length-1;while (left <= right) {int midIndex = left + (right - left)/2;if (A[midIndex] == target) {return midIndex;}if (A[midIndex] <= A[right]) {if (A[midIndex] < target && target <= A[right]) {left = midIndex + 1;} else {right = midIndex - 1;}} else {if (A[left] <= target && target < A[midIndex]) {right = midIndex - 1;} else {left = midIndex + 1;}}}return -1;}
}

 

 

NOTES:

  1. 二分法,但要注意区分mid所处的位置,导致左右区域各是什么情况,是单调有序,还是因转动跨区域;
  2. 假设转动后边界位置为b,如果mid落在边界右边,即[l,b,mid,r], 这是判断目标值和mid值情况,只有tatget在【mid, r】中才能left++,而不是以往target>mid就可以,因为数组转动,target也有可能再左侧区域,同理,如果mid落在边界左边,即[l,mid,b, r],只有tatget在【l, mid】中才能right--。如【3,4,5,6,7,8,0,1,2】,查找1,Vmid=1或7
  相关解决方案