SHARE
TWEET

Untitled

a guest Feb 17th, 2017 54 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  * Search for integer a in sorted array arr[n] similarly to Newton's method
  3.  */
  4. int newtonsearch(int *arr, int n, int a)
  5. {
  6.     int i = 0;
  7.     while (i >= 0 && i < n && arr[i] != a) {
  8.         i -= arr[i] / (arr[i + 1] - arr[i]); // TODO check for boundary conditions, zero denominator, rounding errors
  9.     }
  10.     return i >= 0 && i < n ? i : -1;
  11. }
  12.  
  13. /*
  14.  * Regular binary search on sorted array, analogous to interval cutting for numerical optimization
  15.  */
  16. int binsearch(int *arr, int n, int a)
  17. {
  18.     int max = n - 1, min = 0, mid;
  19.     for (mid = max / 2; min < max && arr[mid] != a; mid = (max + min) / 2) {
  20.         if (arr[mid] > a)
  21.             min = mid;
  22.         else
  23.             max = mid;
  24.     }
  25.     return arr[mid] == a ? mid : -1;
  26. }
RAW Paste Data
Pastebin PRO Summer Special!
Get 60% OFF on Pastebin PRO accounts!
Top