Skip to content

Formula to find median in Binary Search changed #2181

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 3 commits into from
Apr 14, 2021
Merged

Formula to find median in Binary Search changed #2181

Changes from all commits
Commits
Show all changes
3 commits
Select commit Hold shift + click to select a range
bcdc3f0
Formula to find median in BS changed
Apr 13, 2021
70800ff
Fixed bugs
realDuYuanChao Apr 14, 2021
b6258ed
fixed binary search bug
realDuYuanChao Apr 14, 2021
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
2 changes: 1 addition & 1 deletion Searches/BinarySearch.java
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -45,7 +45,7 @@ private <T extends Comparable<T>> int search(T array[], T key, int left, int rig
if (right < left) return -1; // this means that the key not found

// find median
int median = (left + right) >>> 1;
int median = left + ((right-left) >>> 1);
Copy link

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Actually this change is not necessary. Above expression is already using a logical shift (three >>>) which will preserve the sign bit if a potential overflow happens when summing (left + right). For languages like C++ and others that only support arithmetic shift (two >>) above workaround is necessary.

TL;DR original code works fine

int comp = key.compareTo(array[median]);

if (comp == 0) {
Expand Down