Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created April 21, 2018 21:48
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/1bacae4ef04de93ca811f20521bedbce to your computer and use it in GitHub Desktop.
Save jianminchen/1bacae4ef04de93ca811f20521bedbce to your computer and use it in GitHub Desktop.
Find root of number - apply binary search - have a bug, and then fixed on line 29, instead of -1, return start/ 10000.0
using System;
class Solution
{
public static double Root(double x, int n)
{
if(x < 0 || n <= 0)
return -1;
int start = 0;
int end = (int)(Math.Max(1, x) * 10000); // 0.01 -> 0.1
while(start <= end)
{
int middle = start + (end - start)/ 2;
// middle - root(x, n) < 0.001
double middleValue = Math.Pow(middle/ 10000.0, n);
if(Math.Abs(middleValue - x) < 0.001) /// not true, my anaylisy
return middle/ 10000.0;
if(middleValue < x)
start = middle + 1;
else
end = middle - 1;
}
return start/ 10000.0; // x = 7, 0, 0.0001, 0.0002, ..., 1 using binary search 70,000 // bug found in web complier
}
static void Main(string[] args)
{
}
}
/*
keywords:
nonegative number x
n > 0 integer
error of 0.001
ask: root of number, y ^ n = x
given example: x = 7, n = 3, find solution: 1.913
Abs(1.917 - root(x, n)) < 0.001
Binary search -> 0.001
0 - 7 lower bound/ upper bound
increment value -> 0.0001
70000 to search, logn = 10 * log70 = 60 times
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment