Last active
May 10, 2020 01:07
-
-
Save Drawaes/3be787cc5e963e544d92ee4e934799ea to your computer and use it in GitHub Desktop.
Binary Search
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
private async ValueTask<SearchResultValue> BinarySearchBlocks(ReadOnlyMemory<byte> key) | |
{ | |
var min = 0; | |
var max = _metaData.BlockCount - 1; | |
while (min <= max) | |
{ | |
var mid = (min + max) / 2; | |
using var block = await GetKVBlock(mid); | |
var result = block.TryFindKey(key.Span); | |
if (result == BlockReader.KeySearchResult.Found) | |
{ | |
return new SearchResultValue() { Result = SearchResult.Found, Value = block.GetCurrentValue().ToArray() }; | |
} | |
if (result == BlockReader.KeySearchResult.Before) | |
{ | |
max = mid - 1; | |
} | |
else | |
{ | |
min = mid + 1; | |
} | |
} | |
return new SearchResultValue { Result = SearchResult.NotFound }; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment