public class SearchinRotatedSortedArray {
public static int search(int A[], int n, int target)
{
int first=0;
int last=n;
int mid=0;
while(first!=last)
{
mid=(first+last)/2;
if(A[mid]==target)
return mid;
if(A[first]<=A[mid])
{
if(A[first]<=target && target<A[mid])
last=mid;
else
first=mid+1;
}
else
if(A[mid]<target && target<=A[last-1])
first=mid+1;
else
last=mid;
}
return -1;
}
}
2015年7月9日星期四
Search in Rotated Sorted Array
好无聊啊,只有刷题玩玩,让大脑充实一些。有时候刷题不要死脑经去搞懂最基本的东西,能用就行。其实这道题的核心就是找target, 如果target不在搜索区间内就换。
2014年4月15日星期二
Search Insert Position
Problem:
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 → 2[1,3,5,6], 2 → 1[1,3,5,6], 7 → 4[1,3,5,6], 0 → 0
Analysis:
A typical binary search problem.
Solution:
1: public class Solution {
2: public int searchInsert(int[] A, int target) {
3: int high=A.length-1;
4: int low=0;
5: int mid=(high+low)/2;
6: while(low <=high)
7: {
8: mid=(high+low)/2;
9: if(target==A[mid])
10: return mid;
11: if(target>A[mid])
12: low=mid+1;
13: else
14: high=mid-1;
15: }
16: return low;
17: }
18: }
订阅:
博文 (Atom)