Problem of the Day
A new programming or logic puzzle every Mon-Fri

Welcome back to another great Monday! Hope every had a great weekend.

As we do from time to time we'll be revisiting one of the basics of computer algorithms. Create a function that takes in a sorted array of integers and a number. The function should then return the index of that number in the array. If the number doesn't exist return -1. If there is a duplicate you can return either position.

x = [1,2,4,6,7,8,9,10]

binary_basic(x, 4)
>> 2

Comments:

• Anonymous - 10 years, 2 months ago

  C#

  function binary_basic(arr, item) { for(var i = 0; i < arr.Count; i++) { if(arr[i] == item) { return i; } }

  return -1;
  

  }

  reply permalink

• wobblebucket - 10 years, 2 months ago

  def binary_basic(x, y):
      for idx, i in enumerate(x):
          if (y == i): return idx
      return -1
  
  print binary_basic([1, 2, 3, 4, 5, 6, 7, 8], 9)
  

  reply permalink

• Jordi - 10 years, 2 months ago

  REXX: arr = '1 2 4 6 7 8 9 10' do i = 1 to words(arr) w = word(arr,i) say w':' binary_basic(w,arr) end exit

  binary_basic: procedure parse arg s,arr first = 1 last = words(arr) do while first <= last mid = (first+last)%2 if word(arr,mid) == s then, return mid if word(arr,mid) > s then, last = mid-1 else, first = mid+1 end return -1

  reply permalink

• Jordi - 10 years, 2 months ago

  Sorry, didn't know how to format: ''' arr = '1 2 4 6 7 8 9 10' do i = 1 to words(arr) w = word(arr,i) say w':' binary_basic(w,arr) end exit

  binary_basic: procedure parse arg s,arr first = 1 last = words(arr) do while first <= last mid = (first+last)%2 if word(arr,mid) == s then, return mid if word(arr,mid) > s then, last = mid-1 else, first = mid+1 end return -1 '''

  reply permalink

• Anon - 10 years, 2 months ago

  Java

  public static int binaryBasic (int[] x, int num)
  {
          for (int i = 0; i < array.length; i++) {
                  if(array[i] == num) {
                      return i;
                  }
          }
          return -1;
  }
  

  reply permalink

• Anon - 10 years, 2 months ago

  Sorry, in the parameter instead of "int[] x", it should be "int[] array"

  reply permalink

• asheehan - 10 years, 2 months ago

  Tried to do a somewhat crummy binary search in Ruby

  def binary_search(a, i)
      # if length is one, we either have the right answer or we don't
      if a.length == 1
          if a[0] == i
              return 0
          else
              return -i+1
          end
      elsif a.length < 1
          return -i
      end
  
      # if the search int is out of bounds, we have the wrong answer
      if a[0] > i or a[a.length-1] < i
          return -1
      end
  
      # otherwise we compare the middle number and split the array on a mismatch
      mid = (a.length / 2).round
      if a[mid] == i
          return mid
      elsif a[mid] > i
          return binary_search(a[0..mid-1], i)
      else
          return mid+1 + binary_search(a[mid+1..a.length], i)
      end
  end
  
  x = [1,2,4,6,7,8,9,10]
  
  binary_search(x, 5)
  

  reply permalink

• David - 10 years, 2 months ago

  Here is a binary search in Python 2.7

  Demo code included

  import random   # For my generalization test
  
  def binary_basic(inputlist, val, showStepsTaken = 0):
      li = 0
      hi = len(inputlist) - 1
      index = (hi + li)/2
      # I will use the convention that if the middle number is the one I want, I took no steps
      steps = 0   # To demonstrate convergence rate
      while(li != hi):
          if(inputlist[index] == val):
              break
          elif(inputlist[index] < val):
              li = index + 1
              index = (hi + li)/2
          elif(inputlist[index] > val):
              hi = index
              index = (hi + li)/2
          steps += 1
      if(inputlist[index] != val):
          index = -1
      if(showStepsTaken != 0):
          print "%i steps were taken to converge on answer" % steps
      return index
  
  # Now to check agaisnt 1-10
  x = [x + 1 for x in range(10)]
  print "The index in x for 4 is: %i" % binary_basic(x, 4)
  
  # Now to demonstrate step cases on 1-10
  print binary_basic(x, 5, 1)
  print binary_basic(x, 4, 1)
  
  # Now to check against a generated list with a random set of sorted integers
  x = [int(random.random() * 100) for x in range(100)]
  x.sort()
  print x
  print "The index in x for 10 is: %i" % binary_basic(x, 10)
  

  reply permalink