Binary search is commonly used technique in computer science.
Using this technique you can find element in sorted array in O(log n) time complexity.
Below is my implementation of this algorithm.
const binarySearchArr = (arr, target) => {
let [a, b] = [0, arr.length];
let lm;
while (b - a > 0) {
const mid = (a + b) / 2 | 0;
const val = arr[mid];
if (target < val) {
b = mid;
} else if (val < target) {
a = mid;
} else {
return mid;
}
if (lm === mid) break;
lm = mid;
}
return -1;
};
With this function we can very easily solve Search a 2D Matrix task on LeetCode.
Only thing we need yet is converting matrix to array or representing it as array which I implemented using Proxy.
const matrixAsArray = matrix => {
const [h, w] = [matrix.length, matrix[0].length];
return new Proxy([], {
get(target, prop, receiver) {
if (prop === 'length') return h * w;
const idx = +prop;
const col = idx % w;
const row = (idx - col) / w;
return matrix[row][col];
}
});
};
With these two functions solving this task is now trivial as you can see below.
const searchMatrix = (matrix, target) => {
const arr = matrixAsArray(matrix);
return binarySearchArr(arr, target) !== -1;
};
You can play with this code on Instacode.app
I also added both of these functions binarySearchArr and matrixAsArray in my JavaScript Utils collection.
Top comments (3)
Great job on the post and implementation! However, I do have some comments.
Firstly, I think it would be great if you could provide a brief explanation of the algorithm you used and discuss how you might handle any potential edge cases. This would be particularly useful for those who might not be familiar with binary search or similar divide and conquer algorithms. I think it would also make your post more accessible and informative for a wider audience.
Secondly, I was a bit confused by your use of the Proxy object in your implementation. It seems like an unusual choice and I'm not sure I fully understand why you decided to use it. From my perspective, a simpler method for converting the table would probably be just as effective.
Thanks!
I know my posts are very laconic, I know I could put more description but I think tests are doing so better
github.com/gkucmierz/utils/blob/ma...
This proxy solution I am aware that it is pretty strange and original.
You may find it very useful, when you deal with very big data structure (matrix), and you don't want to allocate additional memory.
Another advantage may be when you know that matrix will be modified and you don't want to rewrite this data all the time. I am talking right now about potential real use case, not just solution on LeetCode task.
There is lack of
arrayAsMatrixabstraction to create. Are you open to contribute that? I am ready for PRs.And also docs may be helpful for this utils - I did not implemented that yet.
Thanks for the thorough answer! I haven't stumbled upon a solution using Proxy like that! I will certainly look on that!
Also I would love to read an article of yours explaining this solution