显示标签为“Binary Search”的博文。显示所有博文
显示标签为“Binary Search”的博文。显示所有博文

2015年7月9日星期四

Search in Rotated Sorted Array

好无聊啊,只有刷题玩玩,让大脑充实一些。有时候刷题不要死脑经去搞懂最基本的东西,能用就行。其实这道题的核心就是找target, 如果target不在搜索区间内就换。


 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;  
   }  
 }  

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:  }