Mercurial

annotate grok_interview/binary_search.py @ 55:0dcfbf5ba997

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Remvoing unneeded bzl rules.
author June Park <parkjune1995@gmail.com>
date Fri, 19 Dec 2025 13:59:11 -0800
parents 68fa88ac73fe
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
51
68fa88ac73fe Interview prep for xAI
June Park <parkjune1995@gmail.com>
parents:
diff changeset
1
68fa88ac73fe Interview prep for xAI
June Park <parkjune1995@gmail.com>
parents:
diff changeset
2 x = [1,2,3,4,5,9,20,25,33,99]
68fa88ac73fe Interview prep for xAI
June Park <parkjune1995@gmail.com>
parents:
diff changeset
3 # | |
68fa88ac73fe Interview prep for xAI
June Park <parkjune1995@gmail.com>
parents:
diff changeset
4
68fa88ac73fe Interview prep for xAI
June Park <parkjune1995@gmail.com>
parents:
diff changeset
5 target = 18
68fa88ac73fe Interview prep for xAI
June Park <parkjune1995@gmail.com>
parents:
diff changeset
6 left = 0
68fa88ac73fe Interview prep for xAI
June Park <parkjune1995@gmail.com>
parents:
diff changeset
7 right = len(x)
68fa88ac73fe Interview prep for xAI
June Park <parkjune1995@gmail.com>
parents:
diff changeset
8
68fa88ac73fe Interview prep for xAI
June Park <parkjune1995@gmail.com>
parents:
diff changeset
9 while left < right:
68fa88ac73fe Interview prep for xAI
June Park <parkjune1995@gmail.com>
parents:
diff changeset
10 mid = (left + right)//2
68fa88ac73fe Interview prep for xAI
June Park <parkjune1995@gmail.com>
parents:
diff changeset
11 if x[mid] == target:
68fa88ac73fe Interview prep for xAI
June Park <parkjune1995@gmail.com>
parents:
diff changeset
12 break
68fa88ac73fe Interview prep for xAI
June Park <parkjune1995@gmail.com>
parents:
diff changeset
13 elif x[mid] < target:
68fa88ac73fe Interview prep for xAI
June Park <parkjune1995@gmail.com>
parents:
diff changeset
14 left = mid + 1
68fa88ac73fe Interview prep for xAI
June Park <parkjune1995@gmail.com>
parents:
diff changeset
15 else:
68fa88ac73fe Interview prep for xAI
June Park <parkjune1995@gmail.com>
parents:
diff changeset
16 right = mid
68fa88ac73fe Interview prep for xAI
June Park <parkjune1995@gmail.com>
parents:
diff changeset
17
68fa88ac73fe Interview prep for xAI
June Park <parkjune1995@gmail.com>
parents:
diff changeset
18 print(x[mid])