Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

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
realDuYuanChao 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 2 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

@nirvanarsc nirvanarsc Apr 15, 2021

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
Morty Proxy This is a proxified and sanitized view of the page, visit original site.