## Leetcode 33 search rotation sort array 34 find the first and last position of elements in sorted array 35 search insertion position

Big sai 2020-11-13 06:03:50
leetcode search rotation sort array

## Preface

The last time to punch in before National Day , Continue to open after national day , official account `bigsai` Reply to the group, welcome to join the punch in , If it helps, remember Like collection .

I think everyone is familiar with , Binary search each time judge and compare the range of elements to compress , You can compress half the range every time , So it's too much 1 It's a size you want to see ( The worst ) Spread n Times to the original length .

Many questions are the original dichotomy , But many questions are dichotomous variations .

## 33 Search rotation sort array

This question is actually a dichotomous variant , Some other conditions have been added . Every time the mid To judge how to move . A normal sequence is divided into two sequences , And it's all incremental , There's no same .

Just take the middle mid The value is greater than target There are several situations ：

According to this way of thinking, the other half can be solved all the time .

ac The code is ：

`````` public int search(int[] nums, int target) {

if(nums[0]==target)return 0;
if(nums[nums.length-1]==target)return nums.length-1;
int l=0;int r=nums.length-1;
while (l<r) {

int mid=(l+r)/2;
//System.out.println(mid+" "+l+" "+r);
if(nums[mid]==target)return mid;
// 8 9 2 3 4 5 6 7
if(nums[mid]>target)// The middle is greater than the target
{

if(nums[0]>target) {
// The far left is greater than Only in the smallest area on the right
if(nums[mid]<nums[0])// Currently in the right area
{

r=mid;
}
else {

l=mid+1;
}
}
else {
The far left side is less than the target value towards the left
r=mid;
}
}
// 8 9 2 3 4 5 6 7
else {
// The middle is less than the target
// If it's on the right side, to the left
if(nums[nums.length-1]<target)// The far right side is less than target It needs to go to the left
{

if(nums[mid]<nums[nums.length-1])// At present
{

r=mid;
}
else {

l=mid+1;
}
}
else // The far right is greater than target In a small area
{

l=mid+1;
}
//System.out.println(1);
}
}
return -1;
}
``````

## 34 Find the first and last positions of the elements in the sort array

Two points for beginners , Pay attention to find a value and find the boundary problem in the left and right directions .ac The code is ：

`````` public int[] searchRange(int[] nums, int target) {

int a[]= {
-1,-1};
if(nums.length==1&&nums[0]==target) {
a[0]=0;a[1]=0;return a;}
if(nums.length==0)return a;
int leftindex,rightindex;
int left=0,right=nums.length-1;
while (left<right) {

//System.out.println(left+" "+right);
int mid=(left+right)/2;
if(nums[mid]==target)
{

leftindex=mid;
rightindex=mid;
while (leftindex>=0&&nums[leftindex]==target) {
leftindex--;}
while (rightindex<nums.length&&nums[rightindex]==target) {
rightindex++;}
a[0]=leftindex+1;a[1]=rightindex-1;
return a;
}
else if (nums[mid]<target) {

left=mid+1;
}
else {

right=mid;
}
}
if(nums[left]==target)
{

a[0]=left;a[1]=left;
}
return a;
}
``````

## 35 Search insert location

What we need to pay attention to is the insertion position or the number found . Classic dichotomy doesn't say much about what you know /

`````` public int searchInsert(int[] nums, int target) {

if(nums[0]>=target)return 0;// prune
if(nums[nums.length-1]==target)return nums.length-1;// prune
if(nums[nums.length-1]<target)return nums.length;
int left=0,right=nums.length-1;
while (left<right) {

int mid=(left+right)/2;
if(nums[mid]==target)
return mid;
else if (nums[mid]>target) {

right=mid;
}
else {

left=mid+1;
}
}
return left;
}
``````

At the end of this punch out , There will be a national day break next week ( Just once ). Welcome other brothers and sisters to punch in , WeChat search bigsai, Rejoin the group and join the clasp ！