A Simple Code for an Array Search

Paul Xiong
Oct 22, 2020

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.

--

--

Paul Xiong

Coding, implementing, optimizing ML annotation with self-supervised learning, TLDR: doctor’s labeling is the 1st priority for our Cervical AI project.