GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — JavaScript/Search/ExponentialSearch.js at master · TheAlgorithms/JavaScript Expand file tree/ Copy pathExponentialSearch.jsMore file actions 54 lines (45 loc) · 1.37 KB / Copy pathExponentialSearch.jsFile metadata and controls54 lines (45 loc) · 1.37 KB 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 /** * Exponential Search * * The algorithm consists of two stages. The first stage determines a * range in which the search key would reside if it were in the list. * In the second stage, a binary search is performed on this range. * * * */ function binarySearch(arr, value, floor, ceiling) { // Middle index const mid = Math.floor((floor + ceiling) / 2) // If value is at the mid position return this position if (arr[mid] === value) { return mid } if (floor > ceiling) return -1 // If the middle element is great than the value // search the left part of the array if (arr[mid] > value) { return binarySearch(arr, value, floor, mid - 1) // If the middle element is lower than the value // search the right part of the array } else { return binarySearch(arr, value, mid + 1, ceiling) } } function exponentialSearch(arr, length, value) { // If value is the first element of the array return this position if (arr[0] === value) { return 0 } // Find range for binary search let i = 1 while (i < length && arr[i] <= value) { i = i * 2 } // Call binary search for the range found above return binarySearch(arr, value, i / 2, Math.min(i, length)) } export { binarySearch, exponentialSearch } // const arr = [2, 3, 4, 10, 40, 65, 78, 100] // const value = 78 // const result = exponentialSearch(arr, arr.length, value) |
| You are visitor 01402503 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |