H Index Ii

                                            
class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (citations[mid] == n - mid) {
                return n - mid;
            } else if (citations[mid] < n - mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return n - left;
    }
};

                                            
class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int left = 0, right = n - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (citations[mid] == n - mid) {
                return n - mid;
            } else if (citations[mid] < n - mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return n - left;
    }
}

                                            
class Solution(object):
    def hIndex(self, citations):
        n = len(citations)
        left, right = 0, n - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            if citations[mid] == n - mid:
                return n - mid
            elif citations[mid] < n - mid:
                left = mid + 1
            else:
                right = mid - 1
        
        return n - left

                                            
int hIndex(int* citations, int citationsSize) {
    int left = 0, right = citationsSize - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (citations[mid] == citationsSize - mid) {
            return citationsSize - mid;
        } else if (citations[mid] < citationsSize - mid) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return citationsSize - left;
}

                                            
public class Solution {
    public int HIndex(int[] citations) {
        int n = citations.Length;
        int left = 0, right = n - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (citations[mid] == n - mid) {
                return n - mid;
            } else if (citations[mid] < n - mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return n - left;
    }
}

                                            
/**
 * @param {number[]} citations
 * @return {number}
 */
var hIndex = function(citations) {
    let n = citations.length;
    let left = 0, right = n - 1;
    while (left <= right) {
        let mid = Math.floor(left + (right - left) / 2);
        if (citations[mid] === n - mid) {
            return n - mid;
        } else if (citations[mid] < n - mid) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return n - left;
};

                                            
function hIndex(citations: number[]): number {
    let left = 0;
    let right = citations.length - 1;
    let n = citations.length;
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        if (citations[mid] === n - mid) {
            return n - mid;
        } else if (citations[mid] < n - mid) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return n - left;
};

                                            
class Solution {
    /**
     * @param Integer[] $citations
     * @return Integer
     */
    function hIndex($citations) {
        $n = count($citations);
        
        $left = 0;
        $right = $n - 1;
        
        while ($left <= $right) {
            $mid = $left + floor(($right - $left) / 2);
            
            if ($citations[$mid] == $n - $mid) {
                return $n - $mid;
            } elseif ($citations[$mid] < $n - $mid) {
                $left = $mid + 1;
            } else {
                $right = $mid - 1;
            }
        }
        
        return $n - $left;
    }
}

                                            
class Solution {
    func hIndex(_ citations: [Int]) -> Int {
        var left = 0
        var right = citations.count - 1
        let n = citations.count
        
        while left <= right {
            let mid = left + (right - left) / 2
            if citations[mid] == n - mid {
                return n - mid
            } else if citations[mid] < n - mid {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        
        return n - left
    }
}

                                            
class Solution {
    fun hIndex(citations: IntArray): Int {
        var left = 0
        var right = citations.size - 1
        var n = citations.size

        while (left <= right) {
            val mid = left + (right - left) / 2

            if (citations[mid] == n - mid) {
                return n - mid
            } else if (citations[mid] < n - mid) {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }

        return n - left
    }
}

                                            
class Solution {
  int hIndex(List<int> citations) {
    int n = citations.length;
    int left = 0, right = n - 1;
    while (left <= right) {
      int mid = left + (right - left) ~/ 2;
      if (citations[mid] == n - mid) {
        return n - mid;
      } else if (citations[mid] < n - mid) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    return n - left;
  }
}

                                            
func hIndex(citations []int) int {
    n := len(citations)
    left, right := 0, n-1
    for left <= right {
        mid := left + (right-left)/2
        if citations[mid] == n-mid {
            return n - mid
        } else if citations[mid] < n-mid {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return n - left
}

                                            
# @param {Integer[]} citations
# @return {Integer}
def h_index(citations)
    n = citations.length
    left = 0
    right = n - 1
    
    while left <= right
        mid = left + (right - left) / 2
        if citations[mid] == n - mid
            return n - mid
        elsif citations[mid] < n - mid
            left = mid + 1
        else
            right = mid - 1
        end
    end
    
    return n - left
end

                                            
object Solution {
    def hIndex(citations: Array[Int]): Int = {
        var left = 0
        var right = citations.length - 1
        while (left <= right) {
            val mid = left + (right - left) / 2
            if (citations(mid) >= citations.length - mid) {
                right = mid - 1
            } else {
                left = mid + 1
            }
        }
        citations.length - left
    }
}

                                            
impl Solution {
    pub fn h_index(citations: Vec<i32>) -> i32 {
        let n = citations.len() as i32;
        let (mut left, mut right) = (0, n - 1);
        
        while left <= right {
            let mid = left + (right - left) / 2;
            if citations[mid as usize] == n - mid {
                return n - mid;
            } else if citations[mid as usize] < n - mid {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        n - left
    }
}

                                            
-spec h_index(Citations :: [integer()]) -> integer().
h_index(Citations) ->
    HIndex = h_index(Citations, length(Citations)),
    HIndex.

h_index(_, 0) ->
    0;
h_index(Citations, N) when hd(Citations) >= N ->
    N;
h_index(Citations, N) ->
    h_index(tl(Citations), N-1).

To solve this coding challenge which requires finding the h-index of a researcher using a sorted list of citation counts, it's essential to understand the h-index definition and the requirement for a logarithmic time complexity solution. The h-index represents the maximum number of papers (h) that have received at least h citations each. Our strategy is to utilize binary search due to the logarithmic time complexity constraint.

# Explanation

The problem gives us a sorted array of integers where each integer represents the number of citations a researcher received for their ith paper. We are required to determine the researcher's h-index. According to the h-index definition, it is the largest number h such that the researcher has h papers with at least h citations each. Given the requirement for logarithmic time complexity, binary search is an efficient way to traverse the sorted list of citations:

Binary Search Basics : Binary search repeatedly divides the search interval in half. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half until you find the target value or the interval is empty.
Middle Element Check : For each midpoint determined during the binary search, check if the citations at that point can serve as the h-index.
Conditions :

If
citations[mid] == length - mid

, then
length - mid

is the h-index.
If
citations[mid] < length - mid

, adjust the left boundary of the search.
If
citations[mid] > length - mid

, adjust the right boundary of the search.

# Detailed Steps in Pseudocode

Here, I'll break down the process in detailed pseudocode:

Initialization : Define the initial search boundaries for the binary search.
Binary Search Loop : Continue searching while the left boundary does not exceed the right boundary.

Compute the middle index.
Compare the value at the middle index with the derived h-index condition.
Adjust the search boundaries based on the comparison.

– Return h-index : Once the search is complete, determine the h-index based on the final boundary conditions.

# Pseudocode with Comments

                                            
# Function to find h-index using binary search
function findHIndex(citations):
# Get the total number of citations
total_papers = length(citations) 

# Initialize left and right boundaries for binary search
left = 0 
right = total_papers - 1 

# Start binary search loop
while left <= right:
# Compute midpoint index
mid = left + (right - left) // 2 

# Calculate papers with at least citations[mid] citations
papers_with_at_least_mid_citations = total_papers - mid 

if citations[mid] == papers_with_at_least_mid_citations:
# Found exact h-index
return papers_with_at_least_mid_citations 
elif citations[mid] < papers_with_at_least_mid_citations:
# Move left boundary to the right
left = mid + 1 
else:
# Move right boundary to the left
right = mid - 1 

# Return the h-index when while loop is done
return total_papers - left

# Step-by-Step Explanation

Initialization :

Define two pointers
left

and
right

starting at 0 and the last index of the array, respectively. This sets the boundaries for our binary search.

Binary Search Loop :

Calculate the midpoint index.
Calculate the number of papers that have citations greater than or equal to the value at the midpoint (
papers_with_at_least_mid_citations

).
Compare the value at
citations[mid]

with
papers_with_at_least_mid_citations

.
If they are equal, we've found the h-index because the number of papers having at least
citations[mid]

citations is
citations[mid]

.
If
citations[mid]

is less than
papers_with_at_least_mid_citations

, move the left boundary to
mid + 1

since we're searching for a higher h-index.
If
citations[mid]

is greater than
papers_with_at_least_mid_citations

, move the right boundary to
mid - 1

.

Return h-index :

After exiting the loop, the h-index is determined by
total_papers - left

. The left boundary points to the smallest index where the h-index condition fails, effectively allowing us to derive the correct h-index.

This pseudocode and detailed explanation should help in understanding the process to determine the h-index using binary search within the constraints of logarithmic time complexity.