Saturday, April 25, 2015

Binary search on an array

I read a conference paper lately that has a pseudo code. In the code, there was a binary search and I noticed that the algorithm does not stop. That part in the paper is not very important but I myself confused at first, so I make it clear. 

I took a look at Knuth's TAOCP and I translated the description into Python:




# search key between [l,u]
# returns -1 on failure
def search1(key, arr):
  l = 0
  u = len(arr)-1

  while l<=u:
    m = (l+u)/2
    if arr[m] == key:
      return m
    elif arr[m] > key:
      u = m-1
    else:
      l = m+1
  return -1




This is simple and it has the case for failure.

What happens if the upper limit is an open end? I re-wrote it in this way.

# search key between [l,u)
# you need to be sure that you have an answer in arr
def search2(key,arr):
  l = 0
  u = len(arr)

  while l+1<u:
    m = (l+u)/2
    if arr[m] > key:
      u = m
    else:
      l = m
  return l

It does not have the case for failure so you need to be careful when you call it. There is a trick to compare l and u this case.

The algorithm in the paper is a mix of these and it does not stop. 



Sunday, January 25, 2015

Project Euler memo: Problem 443

Problem 443: GCD sequence. It's interesting and hard. I don't like it. One minute in Python.

Friday, January 23, 2015

Project Euler memo: Problem 497

Problem 497: Drunken Tower of Hanoi. Relatively easy. 24 minutes in Python.

Monday, January 12, 2015

Project Euler memo: Problem 435

Problem 435: Fibonacci coefficient  polynomials. Straightforward computation of Fibonacci numbers with a little trick on modulo inverse. Less than 0.1 seconds in Python.

Sunday, January 11, 2015

Project Euler memo: Problem 430

Problem 430: Flipping discs. A kind of brute force on N. 10 minutes in Golang. I need to learn in the forum later.

Saturday, January 10, 2015

Project Euler memo: Problem 269

Problem 269: One of the two problems left in the 200s. 3 seconds in Python.

Saturday, December 27, 2014

Project Euler memo: Problem 449

Problem 449: Chocolate covered candy. Easier than I thought. 3 seconds in Python and 0.3 seconds in Golang.

Tuesday, December 16, 2014

Project Euler memo: Problem 493

Problem 493: Combination of balls. Very easy but I misunderstood the problem at first. It runs almost immediately in Python.

Project Euler memo: Problem 461

Problem 461: First, I tried to solve this in Golang, and I wrote a terrible algorithm. After I finished it,   I saw the forum,  I tried to do the some thing others did, and I found that Golang consumes a lot of memory for Slice.  I wrote the new one in C++. 10 seconds.

Sunday, December 07, 2014

Project Euler memo: Problem 491

Problem 491: Counting the number of double pan-digital numbers divisible by 11. Easy, but I needed time to debug with a smaller case. Two seconds in Python.