fork download
copy 
  1. // // your code goes here
  2. // function binarySearch(arr, n, target) {
  3. // 	let left=0, right=n-1, mid;
  4. // 	while(left<=right) {
  5. // 		mid = Math.floor((left+right)/2);
  6. // 		if(arr[mid] < target) {
  7. // 			left = mid+1;
  8. // 		} else if(arr[mid] > target) {
  9. // 			right = mid-1;
  10. // 		} else {
  11. // 			return mid;
  12. // 		}
  13. // 	}
  14. // 	return -1;
  15. // }
  16.  
  17. // console.log(binarySearch([2, 4, 5, 7, 8, 9, 11], 7, 8))
  18.  
  19. // 120 -> 60 -> 30 -> 15 -> 7 -> 3 -> 1 --> over
  20.  
  21. // Lower bound: find the index of the first element greater than or equal 
  22. // to a target element
  23. // eg. lowerBound([2, 4, 5, 7, 8, 9, 11], 7, 6) = 3
  24. //     lowerBound([2, 4, 5, 7, 8, 9, 11], 7, 5) = 2
  25. //     lowerBound([2, 4, 5, 7, 8, 9, 11], 7, 13) = -1
  26.  
  27. function lowerBound(arr, n, target) {
  28. 	let left=0, right=n-1, mid;
  29. 	let ans = -1;
  30. 	while(left<=right) {
  31. 		mid = Math.floor((left+right)/2);
  32. 		if(arr[mid] < target) {
  33. 			left = mid+1;
  34. 		} else if(arr[mid] >= target) {
  35. 			ans = mid;
  36. 			right = mid-1;
  37. 		}
  38. 	}
  39. 	return ans;
  40. }
  41.  
  42. // console.log(lowerBound([2, 4, 5, 7, 8, 9, 11], 7, 5))
  43.  
  44. // [2, 4, 5, 7, 8, 9, 11], 7, 5
  45.  
  46. // left=0, right=6, mid = 3, arr[3] = 7 >= 5, ans = 3, right = mid-1
  47. // left=0, right=2, mid = 1, arr[1] = 4 < 5, left = mid+1 = 2
  48. // left=2, right=2, mid = 2, arr[2] = 5 >=5, ans = 2, right = mid-1 = 1
  49. // left=2, right=1
  50.  
  51. // Upper bound: find the index of the first element greater than target element
  52. // eg. upperBound([2, 4, 5, 7, 8, 9, 11], 7, 6) = 3
  53. //     lowerBound([2, 4, 5, 7, 8, 9, 11], 7, 5) = 3
  54. //     lowerBound([2, 4, 5, 7, 8, 9, 11], 7, 13) = -1
  55.  
  56.  
  57. function upperBound(arr, n, target) {
  58. 	let left=0, right=n-1, mid;
  59. 	let ans = -1;
  60. 	while(left<=right) {
  61. 		mid = Math.floor((left+right)/2);
  62. 		if(arr[mid] <= target) {
  63. 			left = mid+1;
  64. 		} else {
  65. 			ans = mid;
  66. 			right = mid-1;
  67. 		}
  68. 	}
  69. 	return ans;
  70. }
  71.  
  72. console.log(upperBound([2, 4, 5, 7, 8, 9, 11], 7, 5))
Success #stdin #stdout 0.03s 16768KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
https://ideone.com/FrJYIf
language:
JavaScript (SMonkey 60.2.3)
created:
6 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!