A Simple Code for an Array Search

Sharp my Python coding skills…

As a senior guy in IT, my most time has spent on architecture and “new technologies”, coding skill has shifted to 2nd place. But, occasionally writing a neat and smart code, still make me feel joy.

A matrix question is:

for each row and column, intergers are sort in ascending, from left to right, top to bottom:
[
  [1,3,7,11]
  [2,5,8,12]
  [10,13,14,17]
  [18,21,23,26]
]
find a numer, return false or true:
5, true
100, false

The idea is simple: trying to

• find the mid-point of a row
• compare the value of the mid-point to trying-to-find-value
• narrow down the search range to the left if less or right, if the mid-point is less or greater than tying-to-find-value
• repeat

        cols= len(matrix[0])
        for row in matrix:
            midpoint = cols // 2
            range_l = 0
            range_r = cols
            while True:
                if row[midpoint] == target:
                    return True
                elif row[midpoint] > target:
                    range_r = midpoint
                elif row[midpoint] < target:
                    range_l = midpoint
                shift = (range_r - range_l) // 2
                midpoint = range_l + shift 
                if shift == 0:
                    if row[midpoint] == target:
                        return True
                    else:
                        break
         return False

To speed up the performance, the above way isn’t the best, but it is neat and easy to understand to me.