Mirror of forum.nim-lang.org

11318 :: i was trying a simple binary search algorithm, what am i doing wrong

• victor_isikwei (orginal) [2024-03-28T21:56:53+01:00] view original

  proc find_x(list: openArray[int], x: int): bool =

  var lo = list.low var hi = list.high

  while lo < hi:

  var m = int((lo + (hi - lo)) / 2)

  if x == list[m]:

  return true

  elif x < list[m]:

  hi = m - 1

  else:

  lo = m

  return false

  var arr: array = [1, 2, 3, 4, 6, 8, 12, 45, 67, 80, 90, 100] stdout.write(find_x(arr, 120))

---

• janAkali (orginal) [2024-03-29T01:42:22+01:00] view original

  Assuming that the code is just wrongly formatted and it looks like this:

  proc find_x(list: openArray[int], x: int): bool =
    var lo = list.low
    var hi = list.high
    
    while lo < hi:
      var m = int((lo + (hi - lo)) / 2)
      if x == list[m]:
        return true
      elif x < list[m]:
        hi = m - 1
      else:
        lo = m
    
    return false
  Run

  You have a small error here:

  var m = int((lo + (hi - lo)) / 2)
  Run

  It should be:

  var m = lo + int((hi+lo) / 2)
  Run

  I would also use integer division instead of converting to int:

  var m = lo + (hi + lo) div 2
  Run

  P.S. You can format code nicely on the forum if you put it in triple backticks, like this:

  ```Nim
  echo "Hello World!"
  ```
  Run

---

• janAkali (orginal) [2024-03-29T02:07:58+01:00] view original

  While loop should use:

  while lo <= hi:
  Run

  Or it would fail on lists of length 1.

  And this change also needed:

  else:
        lo = m + 1
  Run

  Otherwise search gets stuck on last two elements of list, when x > last element.

---

• victor_isikwei (orginal) [2024-03-29T06:43:19+01:00] view original

  Thanks for the response. i will try it out

---

• victor_isikwei (orginal) [2024-03-29T07:07:02+01:00] view original

  echo "Thanks"

  Run

---