KnowledgeHub
Questions
Tags
Users
Search
Alex Rivera
|
Logout
Edit Question
Title
Body
I wonder, can binary search be applied on a 2D array ? What would the conditions on the array be? Sorted on 2D?? What would be the time complexity for it? How would the algorithm change the boundary of the search (minX,maxX,minY,maxY) ?? Edit: Binary Search on 1D maintains 2 pointers minX and maxX .. It selects the middle index (minX+maxX)/2 and compare it with the search value, if greater then change maxX , else change minX ... until minX>=maxX Pseudo code for normal binary seacrh: min := 1; max := N; {array size: var A : array [1..N] of integer} repeat mid := min + (max - min) div 2; if x > A[mid] then min := mid + 1 else max := mid - 1; until (A[mid] = x) or (min > max); Thanks
Tags (comma-separated)
Save Edits
Cancel