# Java O(n) solution using Binary Search

• If a is not 0, we know it's polynomial function, and we wan't to find the global extreme value(the peak value or the valley value, depending on the sign of a); to find peak or valley,we first use Binary Search to find the element in the array which is closest to -b/2a, let's say the index of the element returned from binary search is i,then we use two pointers p1=i-1,p2=i+1, compare nums[p1] and nums[p2], decide which is closer to -b/2a, and move two pointers until both of them are out of index range;if a<0, the iteration of two pointers are outputing elements in descending order(we need to reverse result),if a>0, the output are in acsending order.

if a is 0, we look at b, and this is a linear function; we output element by just iterating nums in array

`````` public class Solution {
public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
int[] res=new int[nums.length];
int index=0;
if(a!=0){
double val=-(double)b/(2*(double)a);
int k=bianrySearch(0,nums.length-1,val,nums);
int i=0;
int j=0;
if(k>=0&&k<nums.length&&nums[k]==val){
res[index]=compute(k,nums,a,b,c);
index++;
i=k-1;
j=k+1;
}else{
i=k-1;
j=k;
}

while(i>=0||j<nums.length){
if(i>=0&&j<nums.length){
if(Math.abs(nums[i]-val)<Math.abs(nums[j]-val)){
res[index]=compute(i,nums,a,b,c);
i--;
}else{
res[index]=compute(j,nums,a,b,c);
j++;
}
}else if(i>=0){
res[index]=compute(i,nums,a,b,c);
i--;
}else{
res[index]=compute(j,nums,a,b,c);
j++;
}
index++;
}

if(a<0){
reverse(res);
}
}else{
if(b<0){
for(int i=nums.length-1;i>=0;i--){
res[nums.length-1-i]=compute(i,nums,a,b,c);
}
}else{
for(int i=0;i<nums.length;i++){
res[i]=compute(i,nums,a,b,c);
}
}
}
return res;
}

public int bianrySearch(int start,int end,double target,int[] nums){
int i=start;
int j=end;
while(i<=j){
int mid=(i+j)/2;
if(nums[mid]==target){
return mid;
}else if(nums[mid]<target){
i=mid+1;
}else{
j=mid-1;
}
}
return i;
}

public int compute(int i,int[] nums,int a,int b,int c){
return a*nums[i]*nums[i]+b*nums[i]+c;
}

public void reverse(int[] nums){
int i=0;
int j=nums.length-1;
while(i<j){
int tmp=nums[i];
nums[i]=nums[j];
nums[j]=tmp;
i++;
j--;
}
}
``````

}

• The thing is, you don't need to find the one which is closest to -b/2a. You can just put the two pointer at two ends of the array and let them go towards each other and meet at -b/2a.

• Try finding first which one is furthest to -b/2a, which is much easier: bound to be at either end.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.