File: code_binary_search.coffee

package info (click to toggle)
firefox 143.0.3-1
  • links: PTS, VCS
  • area: main
  • in suites: sid
  • size: 4,617,328 kB
  • sloc: cpp: 7,478,492; javascript: 6,417,157; ansic: 3,720,058; python: 1,396,372; xml: 627,523; asm: 438,677; java: 186,156; sh: 63,477; makefile: 19,171; objc: 13,059; perl: 12,983; yacc: 4,583; cs: 3,846; pascal: 3,405; lex: 1,720; ruby: 1,003; exp: 762; php: 436; lisp: 258; awk: 247; sql: 66; sed: 53; csh: 10
file content (18 lines) | stat: -rw-r--r-- 532 bytes parent folder | download | duplicates (51) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
# Uses a binary search algorithm to locate a value in the specified array.
window.binary_search = (items, value) ->

  start = 0
  stop  = items.length - 1
  pivot = Math.floor (start + stop) / 2

  while items[pivot] isnt value and start < stop

    # Adjust the search area.
    stop  = pivot - 1 if value < items[pivot]
    start = pivot + 1 if value > items[pivot]

    # Recalculate the pivot.
    pivot = Math.floor (stop + start) / 2

  # Make sure we've found the correct value.
  if items[pivot] is value then pivot else -1